HDOJ 5352 MZL's City 匈牙利匹配

By | 10月04日
Advertisement

求年份和城市的匹配

MZL's City

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 539 Accepted Submission(s): 180

Problem Description

MZL is an active girl who has her own country.

Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:

1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.

2.There is a bidirectional road between city X and city Y built.

3.There is a earthquake happened and some roads were destroyed.

She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.

Input

The first contains one integer T(T<=50),indicating the number of tests.

For each test,the first line contains three integers N,M,K(N<=200,M<=500,K<=200),indicating the number of MZL’s country ,the years happened a big earthquake and the limit of the rebuild.Next M lines,each line contains a operation,and the format is “1 x” , “2 x y”,or a operation of type 3.

If it’s type 3,first it is a interger p,indicating the number of the destoyed roads,next 2*p numbers,describing the p destoyed roads as (x,y).It’s guaranteed in any time there is no more than 1 road between every two cities and the road destoyed must exist in that time.

Output

The First line Ans is the maximal number of the city rebuilt,the second line is a array of length of tot describing the plan you give(tot is the number of the operation of type 1).

Sample Input

1 5 6 2 2 1 2 2 1 3 1 1 1 2 3 1 1 2 1 2

Sample Output

3 0 2 1

Hint

No city was rebuilt in the third year,city 1 and city 3 were rebuilt in the fourth year,and city 2 was rebuilt in the sixth year.

Source

2015 Multi-University Training Contest 5

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月05日 星期三 16时16分29秒
File Name     :HDOJ5352.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn=10010;

int n,m,k;
int mark[maxn];
bool g[202][202],used[maxn];

/*************edge*****************/

struct Edge
{
    int to,next;
}edge[maxn];

int Adj[maxn],Size;

void init()
{
    memset(Adj,-1,sizeof(Adj)); Size=0;
}

void Add_Edge(int u,int v)
{
    edge[Size].to=v;
    edge[Size].next=Adj[u];
    Adj[u]=Size++;
}

void link_edge(int year,int u)
{
    Add_Edge(year,u);
    for(int i=1;i<=n;i++)
    {
        if(g[u][i]==true&&used[i]==false)
        {
            used[i]=true;
            link_edge(year,i);
        }
    }
}

/*************hungary*****************/

int linker[maxn];
bool dfs(int u)
{
    for(int i=Adj[u];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%d%d%d",&n,&m,&k);

        init();
        memset(g,0,sizeof(g));
        memset(mark,0,sizeof(mark));

        for(int i=0,k,x,y;i<m;i++)
        {
            scanf("%d",&k);
            if(k==1)
            {
                scanf("%d",&x);
                memset(used,false,sizeof(used));
                used[x]=true;
                link_edge(i,x);
                mark[i]=true;
            }
            else if(k==2)
            {
                scanf("%d%d",&x,&y);
                g[x][y]=g[y][x]=1;
            }
            else if(k==3)
            {
                int p;
                scanf("%d",&p);
                while(p--)
                {
                    scanf("%d%d",&x,&y);
                    g[x][y]=g[y][x]=0;
                }
            }
        }

        int au=0;
        vector<int> vi;
        memset(linker,-1,sizeof(linker));

        for(int i=m-1;i>=0;i--)
        {
            if(mark[i]==true)
            {
                int tu=0;
                for(int j=0;j<k;j++)
                {
                    memset(used,0,sizeof(used));
                    if(dfs(i)==true) tu++;
                }
                au+=tu;
                vi.push_back(tu);
            }
        }

        printf("%d\n",au);
        for(int sz=vi.size(),i=sz-1;i>=0;i--)
            printf("%d%c",vi[i],(i==0)?'\n':' ');
    }

    return 0;
}

版权声明:来自: 码代码的猿猿的AC之路 http://blog.csdn.net/ck_boss

Similar Posts:

  • HDU 5352 MZL&amp;#39;s City (2015 Multi-University Training Contest 5)

    题目大意: 一个地方的点和道路在M年前全部被破坏,每年可以有三个操作, 1.把与一个点X一个联通块内的一些点重建,2.连一条边,3.地震震坏一些边,每年最多能重建K个城市,问最多能建多少城市,并输出操作要让字典序最小 思路: trivial:显然每年向当年可以建的城市连边,每年可以匹配最多K个城市,嗯,很明显的网络流思路,可这样方案数不太好输出 full:再仔细想想这就是多对一的多重匹配,跑一跑匈牙利就可以,K个城市可以拆点,当然简单的方法直接跑K次也可以(想一想为什么) 为了字典序最小,我们要

  • hdu 5352 MZL&amp;#39;s City 【二分图】

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5352 题意: 给你n,m,k 表示n个建筑 m次操作,修复操作每次最多修复k个建筑. 有三种操作 1.修复x点周围建筑(<=k) 2.x,y建筑间建边 3.x,y间删边 修复建筑时候拆点建图.反着求最大匹配,保证字典序最小. 代码: #include <stdio.h> #include <ctime> #include <math.h> #include <l

  • HDOJ 5349 MZL&amp;#39;s simple problem 【set】

    HDOJ 5349 MZL's simple problem [set] 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5349 set常用场景:operator选择功能实现 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<set> using namespace std; int

  • hdu5352 MZL&amp;#39;s City(最小费用最大流问题)

    题意描述: 一个国家有N个城市,标号1~N,初始时城市和道路都被破坏,下面进行以下三个操作: 第一种操作:1 X 修建城市,和X(包括X自己也可以被修建)直接相连或间接相连的城市可以被一次性修建(但一次性最多修建k个城市) 第二种操作:2 X Y 在X 与 Y之间建立一条道路 第三种操作:3 p X1 Y1 X2 Y2 ··· 表示破坏X1与Y1.X2与Y2之间的道路 经过M次操作后,对于这M次操作中的操作一,我们在每次操作一时修建多少城市修建那些城市才能使最终城市数量最多? 并输出最终修建城市

  • 【HDU5727 2016 Multi-University Training Contest 1E】【状压DP做法 匈牙利匹配做法】Necklace n阳n阴排成环 特定相邻会抑郁 问最少抑郁阳球数

    Necklace Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1872    Accepted Submission(s): 573 Problem Description SJX has 2*N magic gems. N of them have Yin energy inside while others have Yang

  • hdoj.5090 Game with Pearls【二分图匹配】 2015/08/14

    Game with Pearls Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1918 Accepted Submission(s): 674 Problem Description Tom and Jerry are playing a game with tubes and pearls. The rule of the game i

  • hdu 5348 MZL&amp;#39;s endless loop(15多校第五场1006) 欧拉路

    //15多校第五场1006 //hdu5348 MZL's endless loop //若图中都是偶点,那么一定符合条件 //若有奇点,我们的目标就是消除奇点. //从奇点出发,终止于一个奇点变为偶点的位置 //奇点除去一条边变为偶点 //从奇点一直出发直到图中都是偶点,这样直接跑欧拉回路即可. //要证明 //1.从奇点出发只会使奇点变成偶点,不会改变偶点 //2.从奇点出发一定会令图中全是偶点. //3.从奇点出发,终止于奇点的路符和条件 //证明1:从奇点出发不经过偶点,不会使偶点变成奇

  • HDU 5348 MZL&amp;#39;s endless loop(思想用的是深搜)经典

    MZL's endless loop Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1343 Accepted Submission(s): 282 Special Judge Problem Description As we all kown, MZL hates the endless loop deeply, and he co

  • 【ACM】HDOJ 1009 FatMouse&amp;#39; Trade

    HDOJ 1009 Problem Description FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires

  • Hdu 5351 MZL&amp;#39;s Border 2015ACM多校对抗赛第五场

    传送门: http://acm.hdu.edu.cn/showproblem.php?pid=5351 MZL's Border Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 942 Accepted Submission(s): 305 Problem Description As is known to all, MZL is an e

Tags: