1 /* 2 題意：給出一個無向圖，去掉一條權值最小邊，使這個無向圖不再連同！ 3 4 tm太坑了... 5 1,如果這個無向圖開始就是一個非連通圖，直接輸出0 6 2，重邊（兩個節點存在多條邊， 權值不一樣） 7 3，如果找到了橋的最小權值為0，也就是橋上的士兵數為0，那么還是要最少派一個 8 士兵過去炸掉橋！ 9 10 思路：假設每兩個節點最多只有一條邊進行相連！ 11 進行tarjan算法，如果該算法調用了超過2次，說明這個原圖就是不連通的！ 12 否則在tarjan算法中將橋存起來！然后我們遍歷每一座橋，看一看我們找到的 13 橋（連接的兩個定點分別是u, v）是不是(u, v)只有一條路相連接，如果是的， 14 那么就跟新最小值！ 15 */ 16 #include<iostream> 17 #include<cstdio> 18 #include<cstring> 19 #include<algorithm> 20 #define M 1000005 21 #define INF 0x3f3f3f3f 22 #define N 1005 23 using namespace std; 24 struct EDGE{ 25 int u, v, w, nt; 26 EDGE(){} 27 EDGE(int u, int v, int w, int nt){ 28 this->u=u; 29 this->v=v; 30 this->w=w; 31 this->nt=nt; 32 } 33 }; 34 35 EDGE edge[M]; 36 EDGE brige[M]; 37 int first[N]; 38 int low[N], pre[N]; 39 int dfs_clock; 40 int n, m, cnt, ret; 41 42 43 void tarjan(int u, int fa){ 44 low[u]=pre[u]=++dfs_clock; 45 for(int e=first[u]; e!=-1; e=edge[e].nt){ 46 int v=edge[e].v; 47 48 if(!pre[v]){ 49 tarjan(v, u); 50 low[u]=min(low[u], low[v]); 51 if(low[v]>pre[u]) 52 brige[ret++]=edge[e]; 53 } 54 else if(v!=fa && pre[u]>pre[v]) 55 low[u]=min(low[u], pre[v]); 56 } 57 } 58 59 int main(){ 60 while(scanf("%d%d", &n, &m) && (n||m)){ 61 memset(first, -1, sizeof(first)); 62 cnt=0; 63 while(m--){ 64 int u, v, w; 65 scanf("%d%d%d", &u, &v, &w); 66 edge[cnt]=EDGE(u, v, w, first[u]); 67 first[u]=cnt++; 68 edge[cnt]=EDGE(v, u, w, first[v]); 69 first[v]=cnt++; 70 } 71 dfs_clock=0; 72 ret=0; 73 memset(low, 0, sizeof(low)); 74 memset(pre, 0, sizeof(pre)); 75 int flag=0; 76 for(int i=1; i<=n; ++i) 77 if(!pre[i]){ 78 ++flag; 79 if(flag==2) break; 80 tarjan(i, -1); 81 } 82 83 int minNum=INF; 84 if(flag==2) minNum=0; 85 else{ 86 for(int i=0; i<ret; ++i) 87 if(brige[i].w<minNum){//對假定的橋判斷 88 int cc=0; 89 for(int e=first[brige[i].u]; e!=-1; e=edge[e].nt) 90 if(edge[e].v==brige[i].v) ++cc; 91 if(cc==1) minNum=brige[i].w;//說明是真正的橋 92 } 93 if(minNum==INF) minNum=-1; 94 else if(minNum==0) minNum=1;//這一句不要忘記了！ 95 } 96 printf("%d\n", minNum); 97 } 98 return 0; 99 }
?
)
