uvalive 4288 Cat Vs. Dog

题意：

有若干个观看者，要对节目进行投票，每张票一定让一直猫留下，一只狗下场，或者一只狗留下，一只猫下场。

如果某个观看者希望留下的动物下场了，或者希望下场的动物留下了，那么他就会离开。

给出若干个投票信息，求出能够留下的人的最大值。

思路：

假设此时有两个人有矛盾，那么一定是其中一个人希望留下的，另一个人希望下场（反之也成立）。

那么我们就在这两个人之间连一条边，此时就形成了一个二分图。

求留下的人最多，那么就是求离开的人最少，也就是说要用最少的人去覆盖所有的矛盾，那么就转化成了一个求二分图最小点覆盖的问题，二分图的最小点覆盖 = 二分图的最大匹配。

匈牙利算法，复杂度O(n^3)。

代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <vector>
  4 using namespace std;
  5 
  6 const int N = 505;
  7 
  8 int link[N];
  9 bool vis[N];
 10 vector<int> g[N];
 11 
 12 struct node
 13 {
 14     char a,b;
 15     int x,y;
 16     
 17     node(char aa,char bb,int xx,int yy)
 18     {
 19         a = aa;
 20         b = bb;
 21         x = xx;
 22         y = yy;
 23     }
 24 };
 25 
 26 vector<node> vn;
 27 
 28 bool dfs(int u)
 29 {
 30     vis[u] = 1;
 31     
 32     for (int i = 0;i < g[u].size();i++)
 33     {
 34         int to = g[u][i];
 35         
 36         if (!vis[to])
 37         {
 38             vis[to] = 1;
 39             
 40             if (link[to] == -1 || dfs(link[to]))
 41             {
 42                 link[to] = u;
 43                 link[u] = to;
 44                 return true;
 45             }
 46         }
 47     }
 48     
 49     return false;
 50 }
 51 
 52 int solve(int n)
 53 {
 54     int ans = 0;
 55     
 56     for (int i = 0;i < n;i++)
 57     {
 58         if (link[i] == -1)
 59         {
 60             memset(vis,0,sizeof(vis));
 61             if (dfs(i)) ans++;
 62         }
 63     }
 64     
 65     return ans;
 66 }
 67 
 68 int main()
 69 {
 70     int t;
 71     
 72     scanf("%d",&t);
 73     
 74     while (t--)
 75     {
 76         int c,d,v;
 77         
 78         memset(link,-1,sizeof(link));
 79         
 80         scanf("%d%d",&c,&d);
 81         scanf("%d",&v);
 82         
 83         for (int i = 0;i < v;i++) g[i].clear();
 84         vn.clear();
 85         
 86         for (int i = 0;i < v;i++)
 87         {
 88             char a,b;
 89             int x,y;
 90             
 91             scanf(" %c%d",&a,&x);
 92             scanf(" %c%d",&b,&y);
 93             
 94             vn.push_back(node(a,b,x,y));
 95         }
 96         
 97         for (int i = 0;i < v;i++)
 98         {
 99             for (int j = i + 1;j < v;j++)
100             {
101                 if (vn[i].a == vn[j].b && vn[i].x == vn[j].y)
102                 {
103                     g[i].push_back(j);
104                     g[j].push_back(i);
105                 }
106                 else if (vn[j].a == vn[i].b && vn[j].x == vn[i].y)
107                 {
108                     g[i].push_back(j);
109                     g[j].push_back(i);
110                 }
111             }
112         }
113         
114         int res = solve(v);
115         
116         printf("%d
",v - res);
117     }
118     
119     return 0;
120 }