【uva753/poj1087/hdu1526-A Plug for UNIX】最大流

时间:2022-05-19 22:02:08

题意:给定n个插座,m个插头,k个转换器(x,y),转换器可以让插头x转成插头y。问最少有多少个插头被剩下。

题解:

最大流或者二分图匹配。然而我不知道怎么打二分图匹配。。
打了最大流。这题字符串比较坑爹,我就先把所有字符串编号(去重),然后给每个点编两个号,一个代表它作为插头的编号,一个代表它作为插座的编号。
最坑的是uvaWA了好久最后发现结尾要有一个回车。。。。。

还有数据范围也是个坑点,点起码要开500。

 

【uva753/poj1087/hdu1526-A Plug for UNIX】最大流

 

代码如下:(poj上是单组数据,uva和hdu都是多组)

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int N=1010,L=110,INF=(int)1e9;
  9 char s[N][L],c1[L],c2[L];
 10 int ss[N],sc[N],lc[N],rc[N],dis[N],first[N],len,n,m,k,l,num;
 11 struct node{
 12     int x,y,d,next;
 13 }a[100010];
 14 queue<int> q;
 15 
 16 int minn(int x,int y){return x<y ? x:y;}
 17 
 18 void ins(int x,int y,int d)
 19 {
 20     a[++len].x=x;a[len].y=y;a[len].d=d;
 21     a[len].next=first[x];first[x]=len;
 22     a[++len].y=x;a[len].x=y;a[len].d=0;
 23     a[len].next=first[y];first[y]=len;
 24 }
 25 
 26 bool bfs(int st,int ed)
 27 {
 28     while(!q.empty()) q.pop();
 29     memset(dis,-1,sizeof(dis));
 30     q.push(st);dis[st]=0;
 31     while(!q.empty())
 32     {
 33         int x=q.front();q.pop();
 34         for(int i=first[x];i!=-1;i=a[i].next)
 35         {
 36             int y=a[i].y;
 37             if(dis[y]==-1 && a[i].d)
 38             {
 39                 dis[y]=dis[x]+1;
 40                 q.push(y);
 41             }
 42         }
 43     }
 44     return (dis[ed]!=-1);
 45 }
 46 
 47 int dfs(int x,int ed,int flow)
 48 {
 49     if(x==ed) return flow;
 50     int r=0;
 51     for(int i=first[x];i!=-1;i=a[i].next)
 52     {
 53         int y=a[i].y;
 54         if(dis[y]==dis[x]+1 && a[i].d)
 55         {
 56             int p=minn(flow-r,a[i].d);
 57             p=dfs(y,ed,p);
 58             r+=p;
 59             a[i].d-=p;
 60             a[i^1].d+=p;
 61         }
 62     }
 63     if(r==0) dis[x]=-1;
 64     return r;
 65 }
 66 
 67 int dinic(int st,int ed)
 68 {
 69     int ans=0;
 70     while(bfs(st,ed))
 71         ans+=dfs(st,ed,INF);
 72     return ans;
 73 }
 74 
 75 int main()
 76 {
 77     int T;
 78     scanf("%d",&T);
 79     while(T--)
 80     {
 81         int st,ed;
 82         scanf("%d",&n);
 83         l=0;len=-1;
 84         memset(first,-1,sizeof(first));
 85         memset(sc,0,sizeof(sc));
 86         memset(ss,0,sizeof(ss));
 87         for(int i=1;i<=n;i++)
 88         {
 89             scanf("%s",s[++l]);
 90             bool bk=0;
 91             for(int j=1;j<l;j++)
 92             {
 93                 if(strcmp(s[l],s[j])==0) 
 94                 {
 95                     l--,ss[j]++;
 96                     bk=1;break;
 97                 }
 98             }
 99             if(!bk) ss[l]++;
100         }
101         scanf("%d",&m);
102         for(int i=1;i<=m;i++)
103         {
104             scanf("%s",s[++l]);
105             scanf("%s",s[l]);
106             bool bk=0;
107             for(int j=1;j<l;j++)
108             {
109                 if(strcmp(s[j],s[l])==0)
110                 {
111                     l--,sc[j]++;
112                     bk=1;break;
113                 }
114             }
115             if(!bk) sc[l]++;
116         }
117         
118         st=0;num=0;
119         for(int i=1;i<=l;i++)
120         {
121             rc[i]=++num;
122             lc[i]=++num;
123         }    
124         scanf("%d",&k);
125         for(int i=1;i<=k;i++)
126         {
127             scanf("%s%s",c1,c2);
128             int t1=0,t2=0;
129             for(int j=1;j<=l;j++)
130             {
131                 if(strcmp(c1,s[j])==0) t1=j;
132                 if(strcmp(c2,s[j])==0) t2=j;
133                 if(t1 && t2) break;
134             }
135             if(!t1) t1=++l,strcpy(s[l],c1),lc[l]=++num,rc[l]=++num;
136             if(!t2) t2=++l,strcpy(s[l],c2),lc[l]=++num,rc[l]=++num;
137             ins(lc[t1],lc[t2],INF);
138         }
139         ed=num+1;
140         for(int i=1;i<=l;i++)
141         {
142             if(ss[i]) ins(rc[i],ed,ss[i]);
143             if(sc[i]) ins(st,lc[i],sc[i]);
144             ins(lc[i],rc[i],INF);
145         }
146         printf("%d",m-dinic(st,ed));
147         if(T) printf("\n\n");
148         else printf("\n");
149     }
150     return 0;
151 }