HDU5352 MZL's City

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

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.

题目大意

现在有一个初始不连通的图,给出三种操作,2操作为修建公路,3操作是摧毁公路,1操作是对城市x及其所能连通的所有城市进行重建(城市重建后不再会被摧毁),且一次只能重建K个城市。求问MZL一共最多能重建多少个城市,并且在这个前提下对应每一个1操作给出重建城市数目,使得这些答案按照顺序排起来后的字典序最小。


题解

这道题目是一个比较明显的网络流
我们可以建立源点s和汇点t,然后把每一个1操作看成一个点,每一个城市看成一个点。
由源点s向每一个1操作的点连流量为k的边,表示一次1操作最多能够重建k个城市。
由每个城市向汇点t连一条流量为1的边,表示只可能被重建一次。
由每个1操作向这个1操作可以重建的城市连一条流量为1的边,表示这次1操作可以重建这一个城市。
如果这道题只是让求最多的重建城市数目的话,按照上面的建图方式,直接跑最大流就可以了。但是这道题还要求输出重建城市数目的最小字典序的序列。显然直接跑最大流是不行的。
我们可以用最小费用最大流来做这道题。最小费用最大流是在满足最大流的基础上使得费用最小,这一点是十分符合题意的。
具体的方法是,由源点s向每一个1操作的点连的流量为k的边的费用依次减少,其余的边的费用都为0,这样就可以保证字典序最小了。
我们跑一边MCMF,返回流量值不返回费用值,然后对于要求输出的序列,直接扫一遍源点s所连出的所有边的剩余流量,然后用k减去剩余流量,最后加和即可得到。
此外,由于城市较少,我们对于道路的存储最好用邻接图表示,这样会效率更高,并且比邻接表更为简便。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 255;
const int maxk = 255;
const int maxm = 505;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
struct edge{
    int fr,to,cap,dis,id;
    edge(int u,int v,int c,int d) : fr(u),to(v),cap(c),dis(d){};
};
const int INF = 1e9+7;
vectore[maxn+maxm];
vectorg;
vectorconnect;
int mp[maxn][maxn];
int d[maxn+maxm],vis[maxn+maxm],pr[maxn+maxm];
int T,s,t;
int n,m,k;
int cnt,now;
int tot = 0;
void init(){
    cnt = 0;
    for(int i = 0;i <= n+m+1;++i){
        e[i].clear();
    }
    now = INF;
    cnt = 0;tot = 0;
    memset(pr,-1,sizeof(pr));
    g.clear();
    memset(mp,0,sizeof(mp));
    return;
}
bool SPFA(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = INF;
        pr[i] = -1;
        vis[i] = 0;
    }
    queueq;
    d[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = 0;i < e[x].size();++i){
            int v = e[x][i];
            if(d[g[v].to] > d[x] + g[v].dis && g[v].cap > 0){
                pr[g[v].to] = v;
                d[g[v].to] = d[x] + g[v].dis;
                if(!vis[g[v].to]){
                    vis[g[v].to] = 1;
                    q.push(g[v].to);
                }
            }
        }
    }
    return (pr[t] != -1);
}
int mcmf(int s,int t){
    int flow = 0,cost = 0;
    while(SPFA(s,t)){
        int f = INF;
        for(int i = pr[t];i != -1;i = pr[g[i].fr]){
            f = min(f,g[i].cap);
        }
//        for(int i = 0;i <= n+cnt+1;++i)
//            printf("%d ",d[i]);
//        printf("\n");
        flow += f;
        if(d[t] == INF)break;
        cost += d[t] * f;
        for(int i = pr[t];i != -1;i = pr[g[i].fr]){
            g[i].cap -= f;
            g[i^1].cap += f;
        }
    }
    return flow;
}
int opt = 0,u,v,p;
void add(int u,int v,int c,int d){
    g.push_back(edge(u,v,c,d));
    e[u].push_back(tot++);
    g.push_back(edge(v,u,0,-d));
    e[v].push_back(tot++);
    return;
}
void dfs(int x){
    for(int i = 1;i <= n;++i){
        if(mp[x][i] == 1 && !vis[i]){
            connect.push_back(i);
            vis[i] = 1;
            dfs(i);
        }
    }
    return;
}
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        m = get_num();
        k = get_num();
        init();
        memset(mp,0,sizeof(mp));
        s = 0;
        for(int i = 1;i <= n;++i)
            mp[i][i] = 1;
        for(int i = 1;i <= m;++i){
            opt = get_num();
            if(opt == 2){
                u = get_num();
                v = get_num();
                mp[u][v] = 1;
                mp[v][u] = 1;
            }
            else if(opt == 3){
                p = get_num();
                while(p--){
                    u = get_num();
                    v = get_num();
                    mp[u][v] = mp[v][u] = 0;
                }
            }
            else{
                u = get_num();
                cnt++;
                now -= 100;
                add(s,n+cnt,k,now);
                connect.clear();
                memset(vis,0,sizeof(vis));
                dfs(u);
                for(int j = 0;j < connect.size();++j){
                    add(n+cnt,connect[j],1,0);
                }
            }
        }
        t = n + cnt + 1;
        for(int i = 1;i <= n;++i){
            add(i,t,1,0);
        }
        int flow = mcmf(s,t);
        printf("%d\n",flow);
        for(int i = 0;i < e[s].size();++i){
            if(i != e[s].size()-1)
                printf("%d ",k - g[e[s][i]].cap);
            else printf("%d\n",k - g[e[s][i]].cap);
        }
    }
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00