【网络流#4】UVA 753 最大流

news/2023/9/25 4:59:43

最近开始刷网络流的题目了，先从紫书上的开始，这道题是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 }