首页 > 代码库 > 【uva 753】A Plug for UNIX(图论--最大流 Dinic)

【uva 753】A Plug for UNIX(图论--最大流 Dinic)

题意:有N个插头,M个设备和K种转换器。要求插的设备尽量多,问最少剩几个不匹配的设备。

解法:给读入的各种插头编个号,源点到设备、设备通过转换器到插头、插头到汇点各自建一条容量为1的边。跑一次最大流就可得到最多匹配的设备数。

注意啊,我这个代码在神奇?的地方死循环了——判断队列为空的语句......Σ( ° △ °|||)︴所以大家主要看“行文思路” ? :-)

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cstring>  4 #include<algorithm>  5 #include<iostream>  6 #include<queue>  7 using namespace std;  8   9 const int N=110,M=110,K=110; 10 const int NN=310,MM=310,INF=(int)1e9; 11 int n,m,k,ts,st,ed,len; 12 int d[NN],last[NN]; 13 char s[N],ss[N],str[3*N][N];//,sb[M][N]; 14 struct edge{int x,y,fl,next;}a[MM]; 15 queue<int> q; 16  17 int mmin(int x,int y) {return x<y?x:y;} 18 int get_id() 19 { 20     for (int i=1;i<=ts;i++) 21       if (!strcmp(s,str[i])) return i; 22     strcpy(str[++ts],s); 23     return ts; 24 } 25 void ins(int x,int y,int fl) 26 { 27     a[++len].x=x,a[len].y=y,a[len].fl=fl; 28     a[len].next=last[x],last[x]=len; 29     a[++len].x=y,a[len].y=x,a[len].fl=0; 30     a[len].next=last[y],last[y]=len; 31 } 32 bool bfs() 33 { 34     memset(d,-1,sizeof(d)); 35     while(!q.empty()) q.pop();//这里死循环???-_-||| 36     q.push(st); d[st]=1; 37     while (!q.empty()) 38     { 39       int x=q.front(); q.pop(); 40       for (int i=last[x];i;i=a[i].next) 41       { 42         int y=a[i].y; 43         if (d[y]!=-1||!a[i].fl) continue;//fl 44         d[y]=d[x]+1, q.push(y); 45         //if (y==ed) break;//不这样为了第61行的优化 46       } 47     } 48     if (d[ed]==-1) return false; 49     return true; 50 } 51 int dfs(int x,int flow) 52 { 53     if (x==ed) return flow; 54     int sum=0; 55     for (int i=last[x];i;i=a[i].next) 56     { 57       int y=a[i].y; 58       if (d[y]!=d[x]+1||!a[i].fl) continue;// 59       int t=dfs(y, mmin(a[i].fl,flow-sum)); 60       a[i].fl-=t, a[i^1].fl+=t; 61       sum+=t; 62       if (sum==flow) break; 63     } 64     if (sum==0) d[x]=-1;// 65     return sum; 66 } 67 int Dinic() 68 { 69     int sum=0; 70     while (bfs()) 71       sum+=dfs(st,INF);//到这个点时的容量为INF 72     return sum; 73 } 74 int main() 75 { 76     int T,x,y; 77     scanf("%d",&T); 78     while (T--) 79     { 80       st=1,ed=2,len=1,ts=2; 81       scanf("%d",&n); 82       memset(last,0,sizeof(last)); 83       for (int i=1;i<=n;i++) 84       { 85         scanf("%s",s); 86         x=get_id(); 87         ins(x,ed,1); 88       } 89       scanf("%d",&m); 90       for (int i=1;i<=m;i++) 91       { 92         scanf("%s%s",s,s); 93         x=get_id(); 94         ins(st,x,1); 95       } 96       scanf("%d",&k); 97       for (int i=1;i<=k;i++) 98       { 99         scanf("%s",s);100         x=get_id();101         scanf("%s",s);102         y=get_id();103         ins(x,y,1);104       }105       int ans=Dinic();106       if (T) printf("\n");107       printf("%d\n",m-ans);108     }109     return 0;110 }

 

【uva 753】A Plug for UNIX(图论--最大流 Dinic)