poj 1087 A Plug for UNIX(两次Floyd+最小路径覆盖+强大的测试数据)

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

/*
题目：poj 1087 A Plug for UNIX(最小路径覆盖) 
题意：
给定n个插头,m个电器即对应的插座类型,k个转换器(插头A转换为插座B)
求最少有几个电器无法充电
Sample Input
4 
A 
B 
C 
D 
5 
laptop B 
phone C 
pager B 
clock B 
comb X 
3 
B X 
X A 
X D 
Sample Output
1

解题：
第一次Floyd用于确定插座之间的转换关系
第二次Floyd用于确定电器与插座之间的关系
匈牙利算法求最小路径覆盖 
*/
#include<stdio.h>
#include<string.h>
#define M 600
#include<iostream>
using namespace std;
/* 必须将所有出现的插头名称全部存储起来并且编号 */
int G[M][M],GG[M][M];
int n,m,k;
char plugs[M][30];
int p=0;/* 存储插头数组的下标 */
struct node
{
   char from[30];
   char to[30];
   int id;
};
node equip[M];/* 存储电器信息 */
node adapt[M];/* 存储适配器信息 */
int pos(char t[])/* 得到当前插座的位置 */
{
   for(int i=1;i<=p;i++)
   {
      if(strcmp(t,plugs[i])==0)
      return i;
   }
   return 0;
}
void input()/* 输入数据 */
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
   {
       scanf("%s",plugs[i]);
   }
   p=n; 
   scanf("%d",&m);
   for(int i=1;i<=m;i++)
   {
      scanf("%s%s",equip[i].from,equip[i].to);
   }
   scanf("%d",&k);
   for(int i=1;i<=k;i++)
   {
      scanf("%s%s",adapt[i].from,adapt[i].to);
      if(pos(adapt[i].from)==0) 
      {
         p++;
         strcpy(plugs[p],adapt[i].from);
      }
      /* 因为之前给定的插头并不全所以在适配器将没有包含的插头信息加入 */
      if(pos(adapt[i].to)==0)
      {
         p++;
         strcpy(plugs[p],adapt[i].to);
      }
   }
}
void Floyd()/* Floyd求传递闭包 */ 
{
   memset(G,0,sizeof(G));
   for(int i=1;i<=k;i++)/* 建立插座的关联关系*/
   {
      int fro=pos(adapt[i].from);
      int fto=pos(adapt[i].to);
      G[fro][fto]=1;
   }
   for(int s=1;s<=p;s++)/* 求插座的传递闭包 */
   {
      for(int i=1;i<=p;i++)
      {
         for(int j=1;j<=p;j++)
         {
            if(G[i][s]&&G[s][j])
            G[i][j]=1;
         }
      }
   }
   memset(GG,0,sizeof(GG));
   for(int i=1;i<=m;i++)/* 求电器与插座的关联矩阵 */
   {
      int fto=pos(equip[i].to);
      GG[i][fto]=1;
      for(int j=1;j<=n;j++)
      {
         if(G[fto][j])
         GG[i][j]=1;
      }
   }
}
/* 匈牙利算法求最小路径覆盖 */
int link[M],vis[M];
int getnum(int i)/* 寻找增广轨 */
{
   /* 虽然邻接矩阵里的插头数目为p,但是实际插头数目为n,所以范围选定为n */
   for(int j=1;j<=n;j++)
   {
      if(GG[i][j]&&!vis[j])
      {
         vis[j]=1;
         if(link[j]==0||getnum(link[j]))
         {
            link[j]=i;
            return 1;
         }
      }
   }
   return 0;
}
int getans()/* 利用匈牙利算法求最大匹配覆盖 */
{
   int ans=0;
   memset(link,0,sizeof(link));
   for(int i=1;i<=m;i++)
   {
      memset(vis,0,sizeof(vis));
      if(getnum(i)) ans++;
   }
   return ans;
}
int main()
{
   input();
   Floyd();
   /* 输出最小路径覆盖 电器数-最大匹配 */
   printf("%d\n",m-getans());
   return 0;
}