题目描述
某组织打算摧毁发烂稀国的石油运输系统。该系统可以看成一个运输网络,由许多结点和连接结点的管道组成。只有地点A生产石油,生产的石油通过管道运输到地点B,石油不能在中间点累积。管道是双向的,每条管道连接两个不同的结点,每两个结点之间只有一条管道连接。每条管道有一个抗压指数,当石油的流量超过这个数管道就会爆炸。A地生产石油的速度是很快的,但由于抗压指数的问题,能运到B的有一个上限。发烂稀国比较贪婪,他们采用了使他们获得最多石油的运输方案。某组织有一个特殊的物质,能使一条管道的抗压指数下降1。作为该组织的首席程序员,你的任务就是告诉领导,让那些管道的抗压指数下降,一定可以摧毁发烂稀国的石油运输网络。
输入格式
第1行包含四个整数n,m,s,t,表示有n个结点(编号为1,2,3,……,n),m条管道,s和t分别是A地和B地的编号。2<=n<=130, 0<=m<=n (n-1)/2, 1<= s,t <= n。
接下来m行,每行描述一条管道,包含3个整数i, j, c。i, j 分别为管道连接的2个结点。C为该条管道的抗压指数。1<=i, j<=n, 1<=c <=10000。
输出格式
第1行输出抗压指数减少1就爆炸的管道的条数k。
接下来k行每行输出一个整数p(1<=p <=m),说明第p条管道如果抗压指数减少1就必定爆炸。序号p按照管道输入的顺序,并按照p的升序输出。
先Dinic求最大流,最大流的残量网络中用传递闭包找不通的路。Dinic时间复杂度(n^2*m)
#include<iostream> #include<queue> //#include<fstream> using namespace std; //ifstream fin("cin.in"); int n,m,s,t; int lin[131][131]={0},g[9000][3]={0}; int cf[131][131]={0}; int d[131]={0}; bool vis[131]={0}; bool Dinic(){ memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s);d[s]=0;vis[s]=1; while(!Q.empty()) { int e=Q.front();Q.pop(); for(int i=1;i<=lin[e][0];++i) if(!vis[lin[e][i]]&&cf[e][lin[e][i]]) { vis[lin[e][i]]=1; d[lin[e][i]]=d[e]+1; if(lin[e][i]==t) return 1; Q.push(lin[e][i]); } } return 0; } int Findflow(int node,int flow){ if(flow==0||node==t) return flow; int flow1; for(int i=1;i<=lin[node][0];++i) if(d[lin[node][i]]==d[node]+1&&(flow1=Findflow(lin[node][i],min(flow,cf[node][lin[node][i]])))) { cf[node][lin[node][i]]-=flow1; cf[lin[node][i]][node]+=flow1; return flow1; } return 0; } int main() { cin>>n>>m>>s>>t; for(int i=1;i<=m;++i) { cin>>g[i][1]>>g[i][2]; cin>>cf[g[i][1]][g[i][2]]; cf[g[i][2]][g[i][1]]=cf[g[i][1]][g[i][2]]; lin[g[i][1]][0]++; lin[g[i][1]][lin[g[i][1]][0]]=g[i][2]; lin[g[i][2]][0]++; lin[g[i][2]][lin[g[i][2]][0]]=g[i][1]; } while(Dinic()) while(Findflow(s,0xfffffff)); int ans=0; for(int i=1;i<=m;++i) { if(cf[g[i][1]][g[i][2]]>0) cf[g[i][1]][g[i][2]]=1; if(cf[g[i][2]][g[i][1]]>0) cf[g[i][2]][g[i][1]]=1; } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cf[i][j]=max(cf[i][j],cf[i][k]&cf[k][j]); for(int i=1;i<=m;++i) if(cf[g[i][1]][g[i][2]]==0||cf[g[i][2]][g[i][1]]==0) ans++; cout<<ans<<endl; for(int i=1;i<=m;++i) if(cf[g[i][1]][g[i][2]]==0||cf[g[i][2]][g[i][1]]==0) cout<<i<<endl; // system("pause"); return 0; }