HDU 5352 MZL's City (2015 Multi-University Training Contest 5)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意：

一个地方的点和道路在Ｍ年前全部被破坏,每年可以有三个操作,　1.把与一个点Ｘ一个联通块内的一些点重建,2.连一条边,３.地震震坏一些边,每年最多能重建Ｋ个城市,问最多能建多少城市,并输出操作要让字典序最小

思路：

trivial：显然每年向当年可以建的城市连边,每年可以匹配最多Ｋ个城市，嗯，很明显的网络流思路，可这样方案数不太好输出

full:再仔细想想这就是多对一的多重匹配,跑一跑匈牙利就可以,K个城市可以拆点,当然简单的方法直接跑Ｋ次也可以（想一想为什么）

为了字典序最小，我们要尽量让后面的点匹配,所以从后往前跑匹配就可以

 // i love zxr

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define maxn 10009

 using namespace std;

 int matrix[][];

 int nex[maxn],head[maxn],point[maxn],now;

 int mark[maxn],deg[maxn],ans[maxn];

 int visit[maxn],x,y,match[maxn],o,p,n,m,k,h

 ;

 void add(int x,int y)

 {

     nex[++now] = head[x];

     head[x] = now;

     point[now] = y;

 }

 int dfs1(int k,int year)

 {

     visit[k]=;

     add(year,k);

     for(int i=;i<=n;i++)if(matrix[k][i]== && !visit[i])dfs1(i,year);

 }

 int dfs(int k)

 {

     for(int i=head[k];i;i=next[i])

     {

         int u = point[i];

         if(visit[u])continue;

         visit[u]=;

         if(match[u]==- || dfs(match[u]))

         {

             match[u] = k;

             return ;

         }

     }

     return ;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         h=;

         memset(matrix,,sizeof(matrix));

         memset(head,,sizeof(head));

         memset(mark,,sizeof(mark));

         now=;

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

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

         {

             scanf("%d",&o);

             if(o==)

             {

                 scanf("%d",&x);

                 memset(visit,,sizeof(visit));

                 dfs1(x,i);

                 mark[i]=;

             }

             if(o==)

             {

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

                 matrix[x][y] = ;

                 matrix[y][x] = ;

             }

             if(o==)

             {

                 scanf("%d",&p);

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

                 {

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

                     matrix[x][y] = ;

                     matrix[y][x] = ;

                 }

             }

         }

         int an=;

         memset(match,-,sizeof(match));

         for(int i=m;i>=;i--)if(mark[i])

         {

             int u =;

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

             {

                 memset(visit,,sizeof(visit));

                 if(dfs(i))u++;

             }

             an+=u;

             ans[++h]=u;

         }

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

         for(int i=h;i>=;i--)

         {

             printf("%d ",ans[i]);

         }

         if(h)printf("%d\n",ans[]);

     }

     return ;

 }