uvalive 4288 Cat Vs. Dog

题意：

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

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

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

思路：

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

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

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

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

代码：

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 using namespace std;

 const int N = ;

 int link[N];

 bool vis[N];

 vector<int> g[N];

 struct node

 {

     char a,b;

     int x,y;

     node(char aa,char bb,int xx,int yy)

     {

         a = aa;

         b = bb;

         x = xx;

         y = yy;

     }

 };

 vector<node> vn;

 bool dfs(int u)

 {

     vis[u] = ;

     for (int i = ;i < g[u].size();i++)

     {

         int to = g[u][i];

         if (!vis[to])

         {

             vis[to] = ;

             if (link[to] == - || dfs(link[to]))

             {

                 link[to] = u;

                 link[u] = to;

                 return true;

             }

         }

     }

     return false;

 }

 int solve(int n)

 {

     int ans = ;

     for (int i = ;i < n;i++)

     {

         if (link[i] == -)

         {

             memset(vis,,sizeof(vis));

             if (dfs(i)) ans++;

         }

     }

     return ans;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while (t--)

     {

         int c,d,v;

         memset(link,-,sizeof(link));

         scanf("%d%d",&c,&d);

         scanf("%d",&v);

         for (int i = ;i < v;i++) g[i].clear();

         vn.clear();

         for (int i = ;i < v;i++)

         {

             char a,b;

             int x,y;

             scanf(" %c%d",&a,&x);

             scanf(" %c%d",&b,&y);

             vn.push_back(node(a,b,x,y));

         }

         for (int i = ;i < v;i++)

         {

             for (int j = i + ;j < v;j++)

             {

                 if (vn[i].a == vn[j].b && vn[i].x == vn[j].y)

                 {

                     g[i].push_back(j);

                     g[j].push_back(i);

                 }

                 else if (vn[j].a == vn[i].b && vn[j].x == vn[i].y)

                 {

                     g[i].push_back(j);

                     g[j].push_back(i);

                 }

             }

         }

         int res = solve(v);

         printf("%d\n",v - res);

     }

     return ;

 }

巴特西

uvalive 4288 Cat Vs. Dog

最新文章

热门文章