在无向图中找最短桥(tarjan)

题目:hdu 4738

题目意思：曹操有N个岛，这些岛用M座桥连接起来

每座桥有士兵把守(也可能没有)

周瑜想让这N个岛不连通，但只能炸掉一座桥

并且炸掉一座桥需要派出不小于守桥士兵数的人去

解题思路: 首先判断图是否连通，不连通则不需要去炸桥，输出0

图连通，则可以用Tarjan找割边

割边不存在输出-1表示不能达到目的

找到所有的割边，只需要炸掉其中守兵数最少的桥即可

PS: 桥的守兵数为0时，也需要派出一个人去

还要注意一下重边的问题，是重边的话一定不是桥，我用邻接表记录的，是重边的话我就距离变成INF

 1 #include<bits/stdc++.h>
 2 #define mod 1000000007
 3 #define mem(a)  memset(a,0,sizeof(a));
 4 typedef long long ll;
 5 const int INF=0x3f3f3f3f;
 6 using namespace std;
 7 int vim[1003],dfn[1003];
 8 vector<int>q[1003];
 9 int jg[1003][1003];
10 int ans;
11 int top;
12 void tarjan(int x,int fa)
13 { vim[x]=dfn[x]=++top;
14     for(int i:q[x])
15     {  if(i==fa)continue;
16         if(!dfn[i])
17         {
18             tarjan(i,x);
19             vim[x]=min(vim[i],vim[x]);
20            // cout<<vim[i]<<" "<<dfn[x]<<endl;
21             if(vim[i]>dfn[x])
22             {
23                 ans=min(ans,jg[x][i]);
24             }
25         }
26         else
27         {
28             vim[x]=min(vim[x],dfn[i]);
29         }
30     }
31 
32 }
33 int main()
34 {
35   int n,m;
36   while(cin>>n>>m&&n+m){
37   ans=INF;mem(vim);mem(dfn);
38   for(int i=1;i<=n;i++)
39   q[i].clear();
40   memset(jg,0,sizeof(jg));
41   for(int i=1;i<=m;i++)
42   {
43      int a,b,c;
44      cin>>a>>b>>c;
45      q[a].pb(b);
46      q[b].pb(a);
47      if(!jg[a][b]){
48      jg[a][b]=jg[b][a]=c;}
49      else {
50 
51         jg[a][b]=jg[b][a]=INF;
52      }
53   }
54   int q=0;
55   for(int i=1;i<=n;i++)
56     if(!dfn[i])
57       tarjan(i,0),q++;
58       if(q>1)cout<<0<<endl;
59       else if(ans==INF)cout<<-1<<endl;
60       else if(!ans)cout<<1<<endl;
61       else cout<<ans<<endl;
62 }}