Internship

zoj2532:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1532

题意：有n个发射点，m个中继站，然后发射点会发射一些信息给汇点0，这些信息可能会经过中继站，然后给出l条边，每一条都有一个信息容量，现在问你改变哪些边中的任意一条都可以改变这n个点发射信息到0点的总和。

题解：首先，分析一下，要改变的这一条边具有一下性质：

1 这一条边一定是满流的，

2边的起点应该属于残余网络的源点部分，

3边的终点应该是属于残余网络的汇点部分。

所以建图的时候，设置超级源点ss，然后与每个发射点连接，容量是INF，然后跑网络流，从源点深搜，再从汇点神搜，最后遍历每一边，看是否满足以上3条性质。

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 #define INF 100000000

 using namespace std;

 const int N=;

 const int M=;

 struct Node{

    int v;

    int f;

    int next;

 }edge[M];

 int n,m,u,v,l,w,cnt,sx,ex;

 int head[N],pre[N];

 int ans[N],top;

 int from[N],to[N];

 bool vis1[N],vis2[N];

 void init(){

     cnt=;

     memset(head,-,sizeof(head));

     memset(vis1,,sizeof(vis1));

     memset(vis2,,sizeof(vis2));

 }

 void add(int u,int v,int w,int id){

     edge[cnt].v=v;

     edge[cnt].f=w;

     edge[cnt].next=head[u];

     head[u]=cnt++;

     edge[cnt].f=;

     edge[cnt].v=u;

     edge[cnt].next=head[v];

     head[v]=cnt++;

 }

 bool BFS(){

   memset(pre,,sizeof(pre));

   pre[sx]=;

   queue<int>Q;

   Q.push(sx);

  while(!Q.empty()){

      int d=Q.front();

      Q.pop();

      for(int i=head[d];i!=-;i=edge[i].next    ){

         if(edge[i].f&&!pre[edge[i].v]){

             pre[edge[i].v]=pre[d]+;

             Q.push(edge[i].v);

         }

      }

   }

  return pre[ex]>;

 }

 int dinic(int flow,int ps){

     int f=flow;

      if(ps==ex)return f;

      for(int i=head[ps];i!=-;i=edge[i].next){

         if(edge[i].f&&pre[edge[i].v]==pre[ps]+){

             int a=edge[i].f;

             int t=dinic(min(a,flow),edge[i].v);

               edge[i].f-=t;

               edge[i^].f+=t;

             flow-=t;

             if(flow<=)break;

         }

      }

      if(f-flow<=)pre[ps]=-;

       return f-flow;

 }

 void solve(){

     int sum=;

     while(BFS())

         sum+=dinic(INF,sx);

 }

 void DFS1(int u,int fa){

    if(vis1[u])return;

     vis1[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

       if(edge[i].f>){

          DFS1(edge[i].v,u);

       }

    }

 }

 void DFS2(int u,int fa){

    if(vis2[u])return;

     vis2[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

       if(edge[i^].f>){

          DFS2(edge[i].v,u);

       }

    }

 }

 int main() {

     while(~scanf("%d%d%d",&n,&m,&l)&&n) {

          init();

        for(int i=;i<=l;i++){

         scanf("%d%d%d",&from[i],&to[i],&w);

           add(from[i],to[i],w,i);

        }

        for(int i=;i<=n;i++){

          add(m+n+,i,INF,);

        }

        sx=n+m+,ex=;

        solve();

        DFS1(sx,sx);

        DFS2(ex,ex);

        top=;

        for(int i=;i<=l;i++){

            int u=from[i],v=to[i];

          if(vis1[u]&&vis2[v])

             ans[++top]=i;

        }

        if(top==)puts("");

        else{

           sort(ans+,ans+top+);

           for(int i=;i<top;i++)

             printf("%d ",ans[i]);

            printf("%d\n",ans[top]);

        }

     }

     return ;

 }