Hdu 5352 MZL's City (多重匹配)

题目链接：

　　Hdu 5352 MZL's City

题目描述：

　　有n各节点，m个操作。刚开始的时候节点都是相互独立的，一共有三种操作：

　　1：把所有和x在一个连通块内的未重建过的点全部重建。

　　2：建立一条双向路(x,y)

　　3：又发生了地震，p条路被毁。

　　问最后最多有多少个节点被重建，输出重建节点的最小字典序。

解题思路：

　　这几天正好在学匹配，但是昨天下午还是没有看出来这个是匹配题目。看了题解扪心自问了自己三次，是不是傻。就是把每个需要重建的节点x拆成k个点，然后对每个拆分后的点和与拆点在同一连通块里面的点建边，然后按照倒序进行匹配，保证字典序最大。

　　但是匹配好像要比网络流慢好多，改天还是去学一下新姿势的好。

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int N = *;

 vector <int> G[N];

 int ans[maxn*], p[maxn], used[maxn], vis[maxn];

 int n, m, k, num, nu, maps[maxn][maxn];

 void dfs (int u)

 {//求连通块内的点

     vis[u] = ;

     p[num ++] = u;

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

         if (!vis[i] && maps[u][i])

             dfs (i);

 }

 bool Find (int u)

 {

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

     {

         int v = G[u][i];

         if (!vis[v])

         {

             vis[v] = ;

             if (!used[v] || Find(used[v]))

             {

                 used[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int hungry ()

 {

     int res = ;

     memset (used, , sizeof(used));

     for (int i=nu-; i>=; i--)//倒序求最大匹配

         for (int j=i*k; j<(i+)*k; j++)

         {

             memset (vis, , sizeof(vis));

             if (Find(j))

             {

                 res ++;

                 ans[i] ++;

             }

         }

     return res;

 }

 int main ()

 {

     int t;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d %d", &n, &m, &k);

         memset (maps, , sizeof(maps));

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

             G[i].clear();

         nu = ;

         while (m --)

         {

             int type, x, y, z;

             scanf ("%d", &type);

             if (type == )

             {

                 scanf ("%d", &x);

                 num = ;

                 memset (vis, , sizeof(vis));

                 dfs (x);

                 for (int i=; i<num; i++)//建边

                     for (int j=nu*k; j<(nu+)*k; j++)//拆点

                         G[j].push_back(p[i]);

                 nu ++;

             }

             else if (type == )

             {

                 scanf ("%d %d", &x, &y);

                 maps[x][y] = maps[y][x] = ;

             }

             else

             {

                 scanf ("%d", &z);

                 while (z --)

                 {

                     scanf ("%d %d", &x, &y);

                     maps[x][y] = maps[y][x] = ;

                 }

             }

         }

         memset (ans, , sizeof(ans));

         int res = hungry ();

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

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

             printf ("%d%c", ans[i], i==nu-?'\n':' ');

     }

     return ;

 }

巴特西

Hdu 5352 MZL's City (多重匹配)

最新文章

热门文章