首页 > 代码库 > 【网络流#4】UVA 753 最大流
【网络流#4】UVA 753 最大流
最近开始刷网络流的题目了，先从紫书上的开始，这道题是P374上的，嘛，总之这道题最终还是参考了一下紫书。
中间是用了STL中map将字符串映射成编号，使用编号总比是用字符串简单的多。
超级源点S与各个设备对应插头类型连一条边，容量为1，
超级汇点T与各个插头连一条边，容量为1
然后如果有转换器，如果x->y，那么从点x连一条容量为正无穷的边到y (因为插头同类型的有无数个)
这样跑一发最大流即可，代码中间套用模板
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<vector> 10 #include<queue> 11 #include<string> 12 #include<sstream> 13 #define MAXN 405 14 #define MAXM 805 15 #define INF ((1<<30)/2) 16 #define eps 0.000001 17 #define ALL(x) x.begin(),x.end() 18 #define INS(x) inserter(x,x.begin()) 19 using namespace std; 20 int i,j,k,n,m,x,y,T,num,w; 21 22 const int inf = 0x3f3f3f3f; 23 struct edgenode 24 { 25 int from,to,next; 26 int cap; 27 }edge[MAXM]; 28 int Edge,head[MAXN],ps[MAXN],dep[MAXN]; 29 30 void add_edge(int x,int y,int c) 31 { 32 edge[Edge].from=x; 33 edge[Edge].to=y; 34 edge[Edge].cap=c; 35 edge[Edge].next=head[x]; 36 head[x]=Edge++; 37 38 edge[Edge].from=y; 39 edge[Edge].to=x; 40 edge[Edge].cap=0; 41 edge[Edge].next=head[y]; 42 head[y]=Edge++; 43 } 44 45 int dinic(int n,int s,int t) 46 { 47 int tr,res=0; 48 int i,j,k,l,r,top; 49 while(1){ 50 memset(dep,-1,(n+1)*sizeof(int)); 51 for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分，将给定图分层 52 { 53 for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next) 54 { 55 if (edge[j].cap&&-1==dep[k=edge[j].to]) 56 { 57 dep[k]=dep[i]+1;ps[r++]=k; 58 if(k==t) 59 { 60 l=r; 61 break; 62 } 63 } 64 } 65 } 66 if(dep[t]==-1)break; 67 68 for(i=s,top=0;;)//DFS部分 69 { 70 if(i==t)//当前点就是汇点时 71 { 72 for(k=0,tr=inf;k<top;++k) 73 if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; 74 75 for(k=0;k<top;++k) 76 edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr; 77 78 res+=tr; 79 i=edge[ps[top=l]].from; 80 } 81 82 for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点 83 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break; 84 85 if(j!=-1) 86 { 87 ps[top++]=j;//当前点有所指向的点，把这个点加入栈中 88 i=edge[j].to; 89 } 90 else 91 { 92 if (!top) break;//当前点没有指向的点，回溯 93 dep[i]=-1; 94 i=edge[ps[--top]].from; 95 } 96 } 97 } 98 return res; 99 }100 101 int main()102 {103 int T,cas,m,t,n,maxflow,i;104 int x,y,c;105 double ans;106 scanf("%d",&T);107 map <string,int> rec;108 string s,s2;109 while(T--)110 { 111 memset(head,-1,sizeof(head));112 Edge=0;113 scanf("%d",&n);114 rec.clear();115 num=1;//设定，0为源点，1为汇点 116 for (i=1;i<=n;i++)117 {118 cin>>s;119 if (!rec.count(s)) rec[s]=++num; 120 add_edge(rec[s],1,1);121 }122 scanf("%d",&m);123 for (i=1;i<=m;i++)124 {125 cin>>s>>s2;126 if (!rec.count(s2)) rec[s2]=++num; 127 add_edge(0,rec[s2],1);128 }129 scanf("%d",&k);130 for (i=1;i<=k;i++)131 {132 cin>>s>>s2;133 if (!rec.count(s))134 {135 rec[s]=++num;136 }137 if (!rec.count(s2))138 {139 rec[s2]=++num;140 }141 add_edge(rec[s],rec[s2],INF);142 }143 maxflow=dinic(num,0,1);144 printf("%d\n",m-maxflow); 145 if (T!=0) printf("\n");146 }147 return 0;148 }
PS：这道题也是 poj 1087，但是poj中每组测试数据中一组数据，所以要把开始的scanf("%d",&T);去掉
【网络流#4】UVA 753 最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。