题目：http://acm.hdu.edu.cn/showproblem.php?pid=4738
坑点：
- 处理重边
- 图可能不连通，要输出0
- 若求出的结果是0，则要输出1，因为最少要派一个人
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1111; 4 const int inf = 0x3f3f3f3f; 5 struct edge{ 6 int to,cost; 7 }; 8 vector<edge> g[maxn]; 9 int num[maxn],low[maxn],index; 10 int res; 11 int mp[maxn][maxn];//处理两点之间边的条数 12 //tarjan 13 void tarjan(int cur,int father){ 14 index++; 15 num[cur] = index; 16 low[cur] = index; 17 for(int i = 0;i<g[cur].size();i++){ 18 if(num[g[cur][i].to] == 0){ 19 tarjan(g[cur][i].to,cur); 20 low[cur] = min(low[g[cur][i].to],low[cur]); 21 if(low[g[cur][i].to] > num[cur] && mp[cur][g[cur][i].to] == 1) 22 res = min(res,g[cur][i].cost); 23 }else if(g[cur][i].to != father){ 24 low[cur] = min(low[cur],num[g[cur][i].to]); 25 } 26 } 27 } 28 //并查集判断连通性 29 int f[maxn]; 30 int getf(int x){ 31 if(f[x] == x){ 32 return x; 33 }else{ 34 return f[x] = getf(f[x]); 35 } 36 } 37 int merge(int l,int r){ 38 int a = getf(l); 39 int b = getf(r); 40 if(a != b){ 41 f[a] = b; 42 } 43 } 44 // 初始化 45 void init(int n){ 46 index = 0; 47 res = inf; 48 memset(num,0,sizeof(num)); 49 memset(low,0,sizeof(low)); 50 memset(mp,0,sizeof(mp)); 51 for(int i = 1;i<=n;i++){ 52 g[i].clear(); 53 f[i] = i; 54 } 55 } 56 int main(){ 57 int n,m; 58 while(scanf("%d%d",&n,&m) && n && m){ 59 init(n); 60 int a,b,c; 61 while(m--){ 62 scanf("%d%d%d",&a,&b,&c); 63 g[a].push_back(edge{b,c}); 64 g[b].push_back(edge{a,c}); 65 merge(a,b); 66 mp[a][b]++; 67 mp[b][a]++; 68 } 69 int flag = 0; 70 for(int i = 1;i<=n;i++) 71 if(getf(i) != getf(1)){ 72 flag = 1; 73 break; 74 } 75 if(flag){ 76 puts("0"); 77 continue; 78 } 79 tarjan(1,1); 80 if(res == 0) 81 res++; 82 if(res == inf) 83 puts("-1"); 84 else 85 printf("%d ",res); 86 } 87 return 0; 88 }
割边模板：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1111; 4 const int inf = 0x3f3f3f3f; 5 struct edge{ 6 int to,cost; 7 }; 8 vector<edge> g[maxn]; 9 int num[maxn],low[maxn],index; 10 //tarjan 11 void tarjan(int cur,int father){ 12 index++; 13 num[cur] = index; 14 low[cur] = index; 15 for(int i = 0;i<g[cur].size();i++){ 16 if(num[g[cur][i].to] == 0){ 17 tarjan(g[cur][i].to,cur); 18 low[cur] = min(low[g[cur][i].to],low[cur]); 19 if(low[g[cur][i].to] > num[cur]) 20 //u-v为割边 21 }else if(g[cur][i].to != father){ 22 low[cur] = min(low[cur],num[g[cur][i].to]); 23 } 24 } 25 } 26 // 初始化 27 void init(int n){ 28 memset(num,0,sizeof(num)); 29 memset(low,0,sizeof(low)); 30 for(int i = 1;i<=n;i++){ 31 g[i].clear(); 32 } 33 }
割点模板：
1 const int maxn = 1111; 2 const int inf = 0x3f3f3f3f; 3 struct edge{ 4 int to,cost; 5 }; 6 vector<edge> g[maxn]; 7 int num[maxn],low[maxn],index; 8 //tarjan 9 void tarjan(int cur,int father){ 10 int child = 0; 11 index++; 12 num[cur] = index; 13 low[cur] = index; 14 for(int i = 0;i<g[cur].size();i++){ 15 if(num[g[cur][i].to] == 0){ 16 child++; 17 tarjan(g[cur][i].to,cur); 18 low[cur] = min(low[g[cur][i].to],low[cur]); 19 if(low[g[cur][i].to] >= num[cur] && cur!=root) 20 //cur为割点 21 if(cur==root && child>=2) 22 //cur为割点 23 }else if(g[cur][i].to != father){ 24 low[cur] = min(low[cur],num[g[cur][i].to]); 25 } 26 } 27 } 28 // 初始化 29 void init(int n){ 30 memset(num,0,sizeof(num)); 31 memset(low,0,sizeof(low)); 32 for(int i = 1;i<=n;i++){ 33 g[i].clear(); 34 } 35 }