HDU 4685

tiberius 2018-07-19 原文

题意略。

思路：

本题和POJ1904颇为相似，只是那个最大匹配没有现成的，要我们自己求出来。并且要给每一个单身的王子/公主现找一个虚拟的对象。

这也是合乎情理的，王子每一次换一个公主时，可能会导致某一个王子失去他的原配，然而同样也会有另一个单身王子找到公主。

这里注意，每一个虚拟王子要喜欢所有公主，每一个虚拟公主要被所有王子喜欢。

详见代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;

int linked[maxn],component[maxn],V,uN,n,m;
bool used[maxn],visit[maxn];
vector<int> store[maxn];
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> graph[maxn];
vector<int> vs;

void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v] = true;
    for(int i = 0;i < G[v].size();++i){
        int to = G[v][i];
        if(!used[to]) dfs(to);
    }
    vs.push_back(v);
}
void rdfs(int v,int k){
    used[v] = true;
    component[v] = k;
    for(int i = 0;i < rG[v].size();++i){
        int to = rG[v][i];
        if(!used[to]) rdfs(to,k);
    }
}
int scc(){
    memset(used,false,sizeof(used));
    vs.clear();
    for(int v = 1;v <= V;++v){
        if(!used[v]) dfs(v);
    }
    memset(used,false,sizeof(used));
    int k = 0;
    for(int i = vs.size() - 1;i >= 0;--i){
        if(!used[vs[i]]) rdfs(vs[i],k++);
    }
    return k;
}
bool dfs1(int u){
    for(int i = 0;i < graph[u].size();++i){
        int v = graph[u][i];
        if(used[v]) continue;
        used[v] = true;
        if(linked[v] == -1 || dfs1(linked[v])){
            linked[v] = u;
            return true;
        }
    }
    return false;
}
int hungary(){
    int ret = 0;
    memset(linked,-1,sizeof(linked));
    for(int u = 1;u <= uN;++u){
        memset(used,false,sizeof(used));
        if(dfs1(u)) ++ret;
    }
    return ret;
}
void init(){
    memset(component,0,sizeof(component));
    memset(visit,false,sizeof(visit));
    for(int i = 0;i < maxn;++i){
        G[i].clear();
        rG[i].clear();
        store[i].clear();
        graph[i].clear();
    }
    uN = n;
}

int main(){
    int T,cas = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        for(int i = 1;i <= n;++i){
            int ki;
            scanf("%d",&ki);
            int t;
            for(int j = 0;j < ki;++j){
                scanf("%d",&t);
                graph[i].push_back(t);
                add_edge(i,t + n);
            }
        }
        int temp = hungary();
        int tn = n - temp,tm = m - temp;
        for(int i = 1;i <= m;++i){
            int from = i + n,to = linked[i];
            if(to == -1) continue;
            add_edge(from,to);
            visit[to] = true;
        }
        for(int i = n + m + 1;i <= n + m + tm;++i){
            bool signal = true;
            for(int j = n + 1;j <= n + m;++j){
                add_edge(i,j);
                if(signal && linked[j - n] == -1){
                    signal = false;
                    add_edge(j,i);
                    linked[j - n] = i;
                }
            }
        }
        for(int i = n + m + tm + 1;i <= n + m + tm + tn;++i){
            bool signal = true;
            for(int j = 1;j <= n;++j){
                add_edge(j,i);
                if(visit[j] == false && signal){
                    signal = false;
                    visit[j] = true;
                    add_edge(i,j);
                }
            }
        }
        V = n + m + tm + tn;
        int numb = scc();
        for(int i = 1;i <= n;++i){
            for(int j = 0;j < graph[i].size();++j){
                int to = graph[i][j] + n;
                if(to > n + m) continue;
                int belong1 = component[i],
                belong2 = component[to];
                if(belong1 == belong2){
                    store[i].push_back(to - n);
                }
            }
            sort(store[i].begin(),store[i].end());
        }
        printf("Case #%d:\n",cas++);
        for(int i = 1;i <= n;++i){
            printf("%d",store[i].size());
            for(int j = 0;j < store[i].size();++j){
                printf(" %d",store[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}