北极的猴子
Time Limit: 1000 MS Memory Limit: 256 MB
Submit Status
也许你不知道，在北极也有猴子，我们叫它们北极猴。北极猴们在北极一共有n个聚落，不妨叫它们1,2，…n号聚落；它们之间有m条双向道路(这意味着如果一条路从1号聚落到2号聚落，那么你可以过这条路从2号聚落到1号聚落)，每条道路连接2个聚落，且拥有不同的长度。
不过，由于北极没有多少土地，所以它们之间经常为了争夺领土而开战，由此也产生了许多矛盾。这一天，猴子聚落s和猴子聚落t之间便宣布势不两立，北极联合猴协会调解无效后，它们要求摧毁m条道路中的一些路，使得这两个聚落不能互相到达。
猴子们觉得在北极摧毁道路是一件非常费力的事情，于是它们不希望摧毁两条以上的道路。不过，道路长短不一，所以猴子们希望摧毁的道路的总长度最小。
猴子毕竟只是猴子，它们不会算数，所以它们把选择道路的任务交给了你。
Input
第一行两个整数n,m(2≤ n ≤ 5000, 3 ≤ m ≤5000) 表示北极猴聚落的数量和双向道路的数量。
第二行两个不同的整数s,t ( 1≤ s,t ≤ n),表示势不两立的猴子聚落的编号。
接下来m行，每行三个整数x,y,z,( 1≤ x,y ≤ n, 1 ≤ z ≤ 109109 )表示从x到y有一条距离为z的双向道路。
Output
输出一个或两个整数，表示你选择的道路的编号。如果没有需要删除的道路，则输出0.
道路的编号按照输入顺序，记为1,2,…m.
如果输出两个整数，则它们应该不同，且较小的数在前。
如果有多组满足条件的答案，则输出字典序最小的答案。这意味着，如果答案是a,b,则优先选择a最小的答案；若还是有多组，选择b最小的答案。
如果找不到答案，输出-1.
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 4 1 5 1 2 3 2 3 1 3 4 4 4 5 2 |
2 |
5 3 1 5 1 2 3 2 3 1 4 5 2 |
0 |
6 7 1 6 2 1 6 2 3 5 3 4 9 4 6 4 4 6 5 4 5 1 3 1 3 |
2 7 |
Hint
样例1：第二条道路的长度为1，且摧毁之后1号聚落和5号聚落不能互相到达。
Source
2018 UESTC ACM Training for Graph Theory
题解：让你找到一条或者两条边，去掉后是的s和t不再联通。如果找不到输出-1.如果有多个按字典序输出；很明显能看出用无向图的桥处理。
1.首先判断s和t是否相连，如果不相连，输出-1.
2.只去掉一条边，判断是否含有无向图的桥存在，如果存在，输出该边；
3.去掉两条边， 我们可以为每一条打上临时标记，然后可以转化为第2种情况；
4.如果去掉两条边也没有，则输出-1.
AC代码为：
#include<bits/stdc++.h> usingnamespace std; constint INF1=1e8; constint INF2=1e9; struct part{int to,W,net;} e[10010]; struct part1{int id,v;} pre[5010],pre1[5010]; int n,m,s,t,min1,min2,dfn[5010],low[5010],st[5010],cnt,num,cut[10010],vis[5010],flag[10010],h[5001][5001];void addedge(int x,int y,int z){ e[cnt].to=y; e[cnt].W=z; e[cnt].net=st[x]; st[x]=cnt++;}void findcut(int x,int f){ dfn[x]=low[x]=++num;for(int i=st[x];~i;i=e[i].net){if(!dfn[e[i].to]&&!flag[i]){ findcut(e[i].to,x); low[x]=min(low[x],low[e[i].to]);if(low[e[i].to]>dfn[x]&&h[x][e[i].to]==1){ cut[i]=1; cut[i^1]=1;}}elseif(e[i].to!=f &&!flag[i]) low[x]=min(low[x],dfn[e[i].to]);}}int bfs(int x,int y){ queue<int> q; memset(vis,0,sizeof(vis)); q.push(x); pre[x].v=x; vis[x]=1;int v=0;while(!q.empty()){int p=q.front(); q.pop();for(int i=st[p];~i;i=e[i].net){if(!vis[e[i].to]){ vis[e[i].to]=true; pre[e[i].to].v=p; pre[e[i].to].id=i; q.push(e[i].to);}if(e[i].to==y){ v=1;break;}}if(v==1)break;}int ans=-1;while(v==1&& y!=x){if(cut[pre[y].id]==1){if(e[pre[y].id].W<min1){ min1=e[pre[y].id].W; ans=pre[y].id/2+1;}elseif(e[pre[y].id].W==min1&&pre[y].id/2+1<ans) ans=pre[y].id/2+1;} y=pre[y].v;}if(v==0)return10000;elsereturn ans;}int bfs1(int x,int y){ memset(vis,0,sizeof(vis)); memset(pre1,-1,sizeof(pre1)); queue<int> q; pre1[x].v=x; q.push(x); vis[x]=true;int v=0;while(!q.empty()){int p=q.front(); q.pop();for(int i=st[p];~i;i=e[i].net){if(!vis[e[i].to]&& flag[i]==0){ vis[e[i].to]=true; pre1[e[i].to].v=p; pre1[e[i].to].id=i; q.push(e[i].to);}if(e[i].to==y && flag[i]==0){ v=1;break;}}if(v==1)break;}int ans=-1;while(v==1&& y!=x){if(cut[pre1[y].id]==1){if(e[pre1[y].id].W<min2){ min2=e[pre1[y].id].W; ans=pre1[y].id/2+1;}elseif(e[pre1[y].id].W==min2&&pre1[y].id/2+1<ans) ans=pre1[y].id/2+1;} y=pre1[y].v;}return ans;}int main(){ cnt=0; cin>>n>>m>>s>>t;int start=0;for(int i=0;i<=n+1;i++) st[i]=-1;int x,y,z;for(int i=1;i<=m;i++){ cin>>x>>y>>z; h[x][y]+=1; h[y][x]+=1; addedge(x,y,z); addedge(y,x,z); start=x;} memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); num=0; findcut(s,0); min1=INF2;int ans=bfs(s,t);if(ans==10000){ printf("0 ");return(0);}int ans0=ans;int ans1=INF1,ans2=INF1;int tt=t,vv=0;int min3=INF2;while(tt!=s){ flag[pre[tt].id]=1; flag[pre[tt].id^1]=1; h[pre[tt].v][tt]-=1; h[tt][pre[tt].v]-=1; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); findcut(s,0); min2=INF2; ans=bfs1(s,t);if(ans!=-1){if(min2+e[pre[tt].id].W<min3){ min3=min2+e[pre[tt].id].W; ans1=pre[tt].id/2+1; ans2=ans;if(ans1>ans2) swap(ans1,ans2);}elseif(min2+e[pre[tt].id].W==min3){if(min(ans,pre[tt].id/2+1)<ans1){ ans1=min(pre[tt].id/2+1,ans); ans2=max(pre[tt].id/2+1,ans);}elseif(min(pre[tt].id/2+1,ans)==ans1 && max(ans,pre[tt].id/2+1)<ans2){ ans1=min(pre[tt].id/2+1,ans); ans2=max(pre[tt].id/2+1,ans);}if(ans1>ans2) swap(ans1,ans2);} vv=1;} flag[pre[tt].id]=0; flag[pre[tt].id^1]=0; h[pre[tt].v][tt]+=1; h[tt][pre[tt].v]+=1; tt=pre[tt].v;}if(ans0==-1){if(vv==0) cout<<-1<<endl;else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;}else{if(vv==0) cout<<ans0<<endl;else{if(min1<min3) cout<<ans0<<endl;else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;}}return0;}