优惠券网站cms建设,wordpress数据查询插件,求职找工作,网络营销公司怎么赚钱的3046: 招商银行网络系统 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByteTotal Submit: 12 Accepted:3 Description 虽然招商银行的网络安全已经做得非常完善#xff0c;但是天有不测风云#xff0c;招商银行内部网络系统的一台服务器意外感…3046: 招商银行网络系统 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByteTotal Submit: 12 Accepted:3 Description 虽然招商银行的网络安全已经做得非常完善但是天有不测风云招商银行内部网络系统的一台服务器意外感染了一种新型病毒。为了避免更大的损失管理员必须采取紧急措施遏制病毒的蔓延。招商银行内部网络系统共有n台服务器这n台服务器使用m条电缆互相连接。为了描述方便我们给服务器编号1到n。初始时1号服务器感染了病毒。每隔一分钟病毒便会从已感染病毒的服务器扩散到所有与之直接相连的服务器上。招商银行的网络系统设计得非常坚固即使要切断电缆也非常困难。管理员只能在初始时切断一根电缆。为了让整个网络系统尽可能晚地全部被病毒感染他应该切断哪根电缆 Input 输入包含多组数据。每组数据的第一行是两个整数n和m (2≤n≤200, 1≤m≤n*(n-1)/2)其含义如上面所描述。接下来m行每行两个整数a, b (1≤a, b≤n)表示服务器a和服务器b有电缆直接连接。任意两台服务器间至多有一根电缆相连。输入数据以nm0结束。 Output 对每组数据输出最晚多少分钟之后整个网络系统被感染。如果切断某根电缆后病毒永远不会传播到某些服务器那么输出”Great”。 Sample Input 4 51 22 33 44 11 34 41 22 33 41 30 0 Sample Output 2Great 可以想到其实就是到1的最短路 可以想到m*m的但是肯定会超时的啊。不过影响bfs其实就是bfs树上的路径去枚举这些路径就是n*m的复杂度了 #include bits/stdc.h
using namespace std;
#define fi first
#define se second
const int N205;
vectorintG[N];
vectorpairint,intE;
int vis[N],n,cnt,ans;
void bfs(int s,int t)
{memset(vis,0,sizeof vis),cnt0;queuepairint,intQ;Q.push({1,0}),vis[1]1;while(!Q.empty()){pairint,int xQ.front();Q.pop(),ansmax(ans,x.se),cnt;for(auto X:G[x.fi])if(!vis[X](!(Xsx.fit||Xtx.fis)))Q.push({X,x.se1}),vis[X]1;}
}
void la()
{for(int i0; in-1; i){bfs(E[i].fi,E[i].se);if(cntn){coutGreat\n;return;}}coutans\n;
}
int main()
{int m,x;while(cinnm,n||m){ans0,E.clear(),memset(vis,0,sizeof vis);for(int i0,u,v; im; i)cinuv,G[u].push_back(v),G[v].push_back(u);queueintQ;Q.push(1),vis[1]1;while(!Q.empty()){xQ.front(),Q.pop();for(auto X:G[x])if(!vis[X])Q.push(X),E.push_back({x,X}),vis[X]1;}la();for(int i1; in; i)G[i].clear();}
} 转载于:https://www.cnblogs.com/BobHuang/p/10590853.html
