首页 > 代码库 > Internship
Internship
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 }
Internship
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。