【poj 1087 a plug for UNIX】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【poj 1087 a plug for UNIX】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2625字，纯文字阅读大概需要4分钟。
内容图文
在大米饼的帮助下，终于找到了大米饼程序中如同大米饼一般的错误！
考点在问题转化，然后就跑一个你喜欢的最大流算法（二分图可以啵？）
再来一个例子吧：
【纯手绘大米饼图片】
其中有的边权是1，否则就是inf，所以就将问题转化为求超级源点(0)到超级汇点(13)的最大流。我依旧使用ISAP，很开心用ISAP做完了所有老师要求用迪尼克或者艾德蒙·卡普算法做的几个题目，开心点在哪里呢…在乎大米饼之中也。最后一个困扰了me20min的错误是：
把device[i][1]错写成device[i][2],使得CMP函数失效。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<queue>
4 #include<cstring>
5#define go(i,a,b) for(int i=a;i<=b;i++)
6#define fo(i,a,x) for(int i=a[x];i>-1;i=e[i].next)
7#define mem(a,b) memset(a,b,sizeof(a))
8#define inf 1000000000
9usingnamespace std;constint N=90000
;
10
struct E{int v,next,flow,cap;}e[N*20
];
11
char socket[N][30],device[N][2][30],change[N][2][30
];
12
int
n,m,s,t,head[N],k,K,d[N],preE[N],preN[N],cur[N],num[N];
13
void ADD(int u,int v,int flow,int cap){e[K]=(E){v,head[u],flow,cap};head[u]=K++
;}
14
void
Big_Riced_Pancake()
15 {//m(device)--->k(change)--->n(socket) 16 go(i,1,m){ADD(s,i,0,1);ADD(i,s,0,0
);
17 go(j,1,k)if(!strcmp(device[i][1],change[j][0]))ADD(i,j+m,0,inf),ADD(j+m,i,0,0
);
18 go(j,1,n)if(!strcmp(device[i][1],socket[j]))ADD(i,m+k+j,0,1),ADD(m+k+j,i,0,0
);}
19 go(i,1,n)ADD(m+k+i,t,0,1),ADD(t,m+k+i,0,0);go(i,1
,k){
20 go(j,1,k)if((i!=j)&&(!strcmp(change[i][1],change[j][0])))ADD(i+m,j+m,0,inf),ADD(j+m,i+m,0,0
);
21 go(j,1,n)if(!strcmp(change[i][1],socket[j]))ADD(i+m,m+k+j,0,inf),ADD(m+k+j,i+m,0,0
);}
22
}
23
void BFS(){queue<int>q;bool vis[N]={0};q.push(t);vis[t]=1;d[t]=0
;
24
while(!q.empty()){int u=
q.front();q.pop();fo(i,head,u)
25 {int v=e[i].v;if(!vis[v]&&!e[i].cap)vis[v]=1,d[v]=d[u]+1
,q.push(v);}}
26
}
27
int aug(){int u,a=
inf;
28 u=t;while(u!=s){int i=preE[u];a=min(a,e[i].cap-e[i].flow);u=
preN[u];}
29 u=t;while(u!=s){int i=preE[u];e[i].flow+=a;e[i^1].flow-=a;u=preN[u];}return
a;
30
}
31
int main(){scanf("%d",&n);go(i,1,n)scanf("%s"
,socket[i]);
32 scanf("%d",&m);go(i,1,m)go(j,0,1)scanf("%s"
,device[i][j]);
33 scanf("%d",&k);go(i,1,k)go(j,0,1)scanf("%s"
,change[i][j]);
34 mem(head,-1);K=0;s=0;t=n+m+k+1
;Big_Riced_Pancake();
35 BFS();go(i,0,t)num[d[i]]++,cur[i]=head[i];int u=s,flow=0
;
36
while(d[s]<t+1){u==t?flow+=aug(),u=s:1;bool retreat=1
;
37 fo(i,cur,u){int v=e[i].v;if(e[i].cap>e[i].flow&&d[u]==d[v]+1
)
38 {retreat=0;preN[v]=u;cur[u]=preE[v]=i;u=v;break;}}if(!retreat)continue
;
39
int Min=
t;
40 fo(i,head,u){int v=e[i].v;if(e[i].cap>e[i].flow)Min=
min(Min,d[v]);}
41
if(!(--num[d[u]]))break;num[d[u]=Min+1]++;cur[u]=head[u];if(u!=s)u=
preN[u];
42 }printf("%d\n",m-flow);return0
;
43 }//Paul_Guderian
感谢帮我给手稿拍照的同学！
原文：http://www.cnblogs.com/Paul-Guderian/p/6653052.html
内容总结
以上是互联网集市为您收集整理的【poj 1087 a plug for UNIX】全部内容，希望文章能够帮你解决【poj 1087 a plug for UNIX】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。