北极的猴子

Time Limit: 1000 MS     Memory Limit: 256 MB

Submit Status

也许你不知道，在北极也有猴子，我们叫它们北极猴。北极猴们在北极一共有n个聚落，不妨叫它们1,2，…n号聚落；它们之间有m条双向道路(这意味着如果一条路从1号聚落到2号聚落，那么你可以过这条路从2号聚落到1号聚落)，每条道路连接2个聚落，且拥有不同的长度。

不过，由于北极没有多少土地，所以它们之间经常为了争夺领土而开战，由此也产生了许多矛盾。这一天，猴子聚落s和猴子聚落t之间便宣布势不两立，北极联合猴协会调解无效后，它们要求摧毁m条道路中的一些路，使得这两个聚落不能互相到达。

猴子们觉得在北极摧毁道路是一件非常费力的事情，于是它们不希望摧毁两条以上的道路。不过，道路长短不一，所以猴子们希望摧毁的道路的总长度最小。

猴子毕竟只是猴子，它们不会算数，所以它们把选择道路的任务交给了你。

第一行两个整数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的双向道路。

输出一个或两个整数，表示你选择的道路的编号。如果没有需要删除的道路，则输出0.

道路的编号按照输入顺序，记为1,2,…m.

如果输出两个整数，则它们应该不同，且较小的数在前。

如果有多组满足条件的答案，则输出字典序最小的答案。这意味着，如果答案是a,b,则优先选择a最小的答案；若还是有多组，选择b最小的答案。

如果找不到答案，输出-1.

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

样例1：第二条道路的长度为1，且摧毁之后1号聚落和5号聚落不能互相到达。

2018 UESTC ACM Training for Graph Theory    

题解：让你找到一条或者两条边，去掉后是的s和t不再联通。如果找不到输出-1.如果有多个按字典序输出；很明显能看出用无向图的桥处理。            

1.首先判断s和t是否相连，如果不相连，输出-1.

2.只去掉一条边，判断是否含有无向图的桥存在，如果存在，输出该边；

3.去掉两条边，  我们可以为每一条打上临时标记，然后可以转化为第2种情况；    

4.如果去掉两条边也没有，则输出-1.    

AC代码为：        

#include
usingnamespace std;
constint INF1=1e8;
constint INF2=1e9;
struct part{int to,W,net;} e[];
struct part1{int id,v;} pre[],pre1[];
int n,m,s,t,min1,min2,dfn[],low[],st[],cnt,num,cut[],vis[],flag[],h[][];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]==){
cut[i]=;
cut[i^]=;}}elseif(e[i].to!=f &&!flag[i])
low[x]=min(low[x],dfn[e[i].to]);}}int bfs(int x,int y){
queue q;
memset(vis,,sizeof(vis));
q.push(x);
pre[x].v=x;
vis[x]=;int v=;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=;break;}}if(v==)break;}int ans=-;while(v==&& y!=x){if(cut[pre[y].id]==){if(e[pre[y].id].W q;
pre1[x].v=x;
q.push(x);
vis[x]=true;int v=;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]==){
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]==){ v=;break;}}if(v==)break;}int ans=-;while(v==&& y!=x){if(cut[pre1[y].id]==){if(e[pre1[y].id].W>n>>m>>s>>t;int start=;for(int i=;i<=n+;i++) st[i]=-;int x,y,z;for(int i=;i<=m;i++){ cin>>x>>y>>z;
h[x][y]+=;
h[y][x]+=;
addedge(x,y,z);
addedge(y,x,z);
start=x;}
memset(dfn,,sizeof dfn);
memset(low,,sizeof low);
num=;
findcut(s,);
min1=INF2;int ans=bfs(s,t);if(ans==){
printf("0\n");return();}int ans0=ans;int ans1=INF1,ans2=INF1;int tt=t,vv=;int min3=INF2;while(tt!=s){
flag[pre[tt].id]=;
flag[pre[tt].id^]=;
h[pre[tt].v][tt]-=;
h[tt][pre[tt].v]-=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(cut,,sizeof(cut));
findcut(s,);
min2=INF2;
ans=bfs1(s,t);if(ans!=-){if(min2+e[pre[tt].id].Wans2) swap(ans1,ans2);}elseif(min2+e[pre[tt].id].W==min3){if(min(ans,pre[tt].id/+)ans2) swap(ans1,ans2);}
vv=;}
flag[pre[tt].id]=;
flag[pre[tt].id^]=;
h[pre[tt].v][tt]+=;
h[tt][pre[tt].v]+=;
tt=pre[tt].v;}if(ans0==-){if(vv==) cout<<-<<endl;else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;}else{if(vv==) cout<<ans0<<endl;else{if(min1<min3) cout<<ans0<<endl;else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;}}return0;}