首页 > 代码库 > Internship

Internship

2024-07-21 05:23:07   220人阅读

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

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

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

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

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

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

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

  1 #include<iostream>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdio>  5 #include<queue>  6 #define INF 100000000  7 using namespace std;  8 const int N=1305;  9 const int M=40000; 10 struct Node{ 11    int v; 12    int f; 13    int next; 14 }edge[M]; 15 int n,m,u,v,l,w,cnt,sx,ex; 16 int head[N],pre[N]; 17 int ans[N],top; 18 int from[N],to[N]; 19 bool vis1[N],vis2[N]; 20 void init(){ 21     cnt=0; 22     memset(head,-1,sizeof(head)); 23     memset(vis1,0,sizeof(vis1)); 24     memset(vis2,0,sizeof(vis2)); 25 } 26 void add(int u,int v,int w,int id){ 27     edge[cnt].v=v; 28     edge[cnt].f=w; 29     edge[cnt].next=head[u]; 30     head[u]=cnt++; 31     edge[cnt].f=0; 32     edge[cnt].v=u; 33     edge[cnt].next=head[v]; 34     head[v]=cnt++; 35 } 36 bool BFS(){ 37   memset(pre,0,sizeof(pre)); 38   pre[sx]=1; 39   queue<int>Q; 40   Q.push(sx); 41  while(!Q.empty()){ 42      int d=Q.front(); 43      Q.pop(); 44      for(int i=head[d];i!=-1;i=edge[i].next    ){ 45         if(edge[i].f&&!pre[edge[i].v]){ 46             pre[edge[i].v]=pre[d]+1; 47             Q.push(edge[i].v); 48         } 49      } 50   } 51  return pre[ex]>0; 52 } 53 int dinic(int flow,int ps){ 54     int f=flow; 55      if(ps==ex)return f; 56      for(int i=head[ps];i!=-1;i=edge[i].next){ 57         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 58             int a=edge[i].f; 59             int t=dinic(min(a,flow),edge[i].v); 60               edge[i].f-=t; 61               edge[i^1].f+=t; 62             flow-=t; 63             if(flow<=0)break; 64         } 65  66      } 67      if(f-flow<=0)pre[ps]=-1; 68       return f-flow; 69 } 70 void solve(){ 71     int sum=0; 72     while(BFS()) 73         sum+=dinic(INF,sx); 74 } 75 void DFS1(int u,int fa){ 76    if(vis1[u])return; 77     vis1[u]=1; 78    for(int i=head[u];i!=-1;i=edge[i].next){ 79       if(edge[i].f>0){ 80          DFS1(edge[i].v,u); 81       } 82    } 83 } 84 void DFS2(int u,int fa){ 85    if(vis2[u])return; 86     vis2[u]=1; 87    for(int i=head[u];i!=-1;i=edge[i].next){ 88       if(edge[i^1].f>0){ 89          DFS2(edge[i].v,u); 90       } 91    } 92 } 93 int main() { 94     while(~scanf("%d%d%d",&n,&m,&l)&&n) { 95          init(); 96        for(int i=1;i<=l;i++){ 97         scanf("%d%d%d",&from[i],&to[i],&w); 98           add(from[i],to[i],w,i); 99        }100        for(int i=1;i<=n;i++){101          add(m+n+1,i,INF,0);102        }103        sx=n+m+1,ex=0;104        solve();105        DFS1(sx,sx);106        DFS2(ex,ex);107        top=0;108        for(int i=1;i<=l;i++){109            int u=from[i],v=to[i];110          if(vis1[u]&&vis2[v])111             ans[++top]=i;112        }113        if(top==0)puts("");114        else{115           sort(ans+1,ans+top+1);116           for(int i=1;i<top;i++)117             printf("%d ",ans[i]);118            printf("%d\n",ans[top]);119        }120     }121     return 0;122 }
View Code

 

Internship


联系
我们