TOJ 3046: 招商銀行網絡系統

3046: 招商銀行網絡系統?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total 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有電纜直接連接。任意兩臺服務器間至多有一根電纜相連。
輸入數據以n=m=0結束。

Output

對每組數據輸出最晚多少分鐘之后整個網絡系統被感染。如果切斷某根電纜后病毒永遠不會傳播到某些服務器，那么輸出”Great”。

Sample Input

4 5
1 2
2 3
3 4
4 1
1 3
4 4
1 2
2 3
3 4
1 3
0 0

Sample Output

2
Great

可以想到其實就是到1的最短路

可以想到m*m的，但是肯定會超時的啊。不過影響bfs其實就是bfs樹上的路徑，去枚舉這些路徑就是n*m的復雜度了

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=205;
vector<int>G[N];
vector<pair<int,int>>E;
int vis[N],n,cnt,ans;
void bfs(int s,int t)
{memset(vis,0,sizeof vis),cnt=0;queue<pair<int,int>>Q;Q.push({1,0}),vis[1]=1;while(!Q.empty()){pair<int,int> x=Q.front();Q.pop(),ans=max(ans,x.se),cnt++;for(auto X:G[x.fi])if(!vis[X]&&(!(X==s&&x.fi==t||X==t&&x.fi==s)))Q.push({X,x.se+1}),vis[X]=1;}
}
void la()
{for(int i=0; i<n-1; i++){bfs(E[i].fi,E[i].se);if(cnt<n){cout<<"Great\n";return;}}cout<<ans<<"\n";
}
int main()
{int m,x;while(cin>>n>>m,n||m){ans=0,E.clear(),memset(vis,0,sizeof vis);for(int i=0,u,v; i<m; i++)cin>>u>>v,G[u].push_back(v),G[v].push_back(u);queue<int>Q;Q.push(1),vis[1]=1;while(!Q.empty()){x=Q.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 i=1; i<=n; i++)G[i].clear();}
}

?

?