poj 1087 A Plug for UNIX(两种做法+强大的测试数据)

符本题的一组强大的测试数据 http://www.cnblogs.com/penseur/archive/2011/05/17/2049167.html

符另一种二分图求最小路径覆盖的做法 http://www.cnblogs.com/penseur/archive/2011/05/17/2049171.html

/*
解题：利用网络流的EK算法求最大流
利用网络流求最大流
原点到电器的容量为1 
电器到插头的容量为1
插头到插头的容量为INF
插头到终点的容量为1
原点与终点需自己加上,不妨设原点为1,终点为2
建好图以后,下面就是赤裸裸的求最大流的问题了
结果=m-最大流 
*/
#include<map>
#include<cstring>
#include<cstdio> 
#include<iostream>
#define INF 0x7FFFFFFF
#define M 500
using namespace std;
map<string,int>hash;
int G[M][M],f[M],pre[M],queue[M];
/* 设定初始点start=1，终点end为2，cnt用于记录网络流中节点的个数 */
int n,m,k,start=1,end=2,cnt=2;
void exists(char s[])/* 对当前字符串hash */ 
{
   if(hash[s]==0)
   {
      cnt++;
      hash[s]=cnt;  
   }
}
void input()/* 输入数据 */ 
{
   memset(G,0,sizeof(G));
   scanf("%d",&n);
   char str1[30],str2[30];
   for(int i=1;i<=n;i++)
   {
      scanf("%s",str1);
      cnt++;
      hash[str1]=cnt;
      G[cnt][end]=1;/* 插头与终点连接容量为1 */  
   }
   scanf("%d",&m);
   for(int i=1;i<=m;i++)
   {
      scanf("%s%s",str1,str2);
      exists(str1);
      exists(str2);
      int t1=hash[str1];
      int t2=hash[str2];
      G[t1][t2]=1;/* 电器与插座相连容量为1 */
      G[start][t1]=1;/* 电器与原点相连容量为1 */
   }
   scanf("%d",&k);
   for(int i=1;i<=k;i++)
   {
      scanf("%s%s",str1,str2);
      exists(str1);
      exists(str2);
      int t1=hash[str1];
      int t2=hash[str2];
      G[t1][t2]=INF;/* 插座与终点相连容量为无穷 */
   }
}
int bfs()/* 广度搜索 */
{
   memset(pre,-1,sizeof(pre));
   for(int i=1;i<=cnt;i++)
   f[i]=INF;
   int tail=0,head=-1,cur;
   queue[0]=start;
   while(head<tail)
   {
      head++;
      cur=queue[head];
      if(cur==end)
      return f[end];
      for(int i=1;i<=cnt;i++)
      {
         /* 注意pre[i]!=-1 */
         if(pre[i]!=-1||G[cur][i]==0)
         continue;
         f[i]=min(f[cur],G[cur][i]);
         pre[i]=cur;
         tail++;
         queue[tail]=i;
      }
   }
   return -1;
}
int EK()/* 利用EK算法 */
{
   int ans=0;
   while(1)
   {
      int tmp=bfs();
      if(tmp==-1)
      return ans;
      ans+=tmp;
      int next,cur=end;
      while(cur!=start)
      {
         next=cur;
         cur=pre[cur];
         G[cur][next]-=tmp;
         G[next][cur]+=tmp;
      }
   }
}
int main()
{
   input();
   printf("%d\n",m-EK());
   return 0;
}