hdu 4685 Prince and Princess

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分图 + 强连通分量

题意：略，和poj 1904差不多

  1. 对图求一次二分匹配，得到最大匹配数为res
  2. 因为男女人数不一定相同，题目也没有保证一定有完备匹配，所以当最大匹配为res的时候，男方有n-res个点没有匹配，女方有m-res个点没有匹配。
  3. 对于每一个没有匹配的男方，都虚构一个女子出来，直接跟他匹配，那么一共虚构出n-res个女子；对于每一个没有匹配的女方，都虚构出一个男子，直接跟她匹配，那么一共虚构出m-res个女子。可知，虚构完成后，男女方的人数都输，n+m-res。这样做就得到了一个完备匹配
  4. 此时，男女方点数都是n+m-res。对于每个虚构的男子，它喜欢所有n+m-res个女子，连n+m-res条边；对于每个虚构的女子，它被所有n+m-res个男子喜欢，被连n+m-res条边；这样整个图就构造完成
  5. 对于这个图，就回到了poj 1904的做法，对于每个男子，找到和它匹配的女子，为wife，然后看看这个男子还喜欢什么女子v，wife —> v，这样就构好了有向图，在这个有向图上求一次SCC
  6. 然后看看wife处在哪个连通分量，如果喜欢的v也在这个连通分量，则加进来。注意，虚构的v就没必要加了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 1010
#define M 5000010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,m;
bool g[N][N],vis[N];
int xmatch[N],ymatch[N];
int tot,head[N];
int ans[N][N],num[N];
struct edge{
    int u,v,next;
}e[M];
int dfn[N],low[N],belong[N],stack[N],top,dcnt,bcnt;
bool ins[N];

int dfs(int u){
    for(int v = 1; v <= m; v++)
        if(g[u][v] && !vis[v]){
            vis[v] = true;
            if(ymatch[v] == -1 || dfs(ymatch[v])){
                xmatch[u] = v; ymatch[v] = u; return 1;
            }
        }
    return 0;
}

int MaxMatch(){
    int ans = 0;
    cl(xmatch,-1); cl(ymatch,-1);
    for(int u = 1; u <= n; u++){
        cl(vis,false);
        ans += dfs(u);
    }
    return ans;
}

inline void add(int u,int v){
    e[tot].u = u; e[tot].v = v;
    e[tot].next = head[u]; head[u] = tot++;
}

void tarjan(int u){
    dfn[u] = low[u] = ++dcnt;
    stack[++top] = u; ins[u] = true;
    for(int k = head[u]; k != -1; k = e[k].next){
        int v = e[k].v;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(ins[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        ++bcnt;
        while(true){
            int x = stack[top--];
            belong[x] = bcnt; ins[x] = false;
            if(x == u) break;
        }
    }
}

void SCC(int nn){
    dcnt = bcnt = top = 0;
    cl(dfn,0); cl(ins,false);
    for(int i = 1; i <= nn; i++)
        if(!dfn[i])
            tarjan(i);
}

int main(){
    int T;
    scanf("%d",&T);
    for(int cas = 1; cas <= T; cas++){
        scanf("%d%d",&n,&m);
        cl(g,false);
        for(int u = 1; u <= n; u++){
            int k,v;
            scanf("%d",&k);
            while(k--){
                scanf("%d",&v);
                g[u][v] = true;
            }
        }
        int res = MaxMatch();
        
        for(int u = 1,cnt = 0; u <= n; u++)
            if(xmatch[u] == -1){ //王子没有匹配
                xmatch[u] = m + (++cnt); //虚构一个新的公主和他匹配
                ymatch[m+cnt] = u;
                g[u][m+cnt] = true; //连一条边
            }
        for(int v = 1,cnt = 0; v <= m; v++)
            if(ymatch[v] == -1){ //公主没有匹配
                ymatch[v] = n + (++cnt); //虚构一个新的王子和他匹配
                xmatch[n+cnt] = v;
                g[n+cnt][v] = true;
            }
        for(int u = n+1; u <= n+m-res; u++) //新虚构出来的王子，每一个都喜欢所有公主
            for(int v = 1; v <= n+m-res; v++)
                g[u][v] = true;
        for(int v = m+1; v <= n+m-res; v++) //新虚构出来的公主，每一个都被所有王子喜欢
            for(int u = 1; u <= n+m-res; u++)
                g[u][v] = true;

        cl(head,-1); tot = 0;
        for(int u = 1; u <= n+m-res; u++){
            int wife = xmatch[u];
            for(int v = 1; v <= n+m-res; v++)
                if(g[u][v] && v != wife)
                    add(wife,v);
        }
        /*
        for(int u = 1; u <= n+m-res; u++){
            printf("%d : ",u);
            for(int k = head[u]; k != -1; k = e[k].next){
                int v = e[k].v;
                printf("%d ",v);
            }
            puts("");
        }
        */
        SCC(n+m-res);
        printf("Case #%d:\n",cas);
        cl(num,0);
        for(int u = 1; u <= n; u++){ //不需要看虚构的王子
            int wife = xmatch[u];
            int bw = belong[wife];
            if(wife <= m) ans[u][num[u]++] = wife;
            for(int k = head[wife]; k != -1; k = e[k].next){
                int v = e[k].v;
                if(v > m) continue; //虚构的直接抛弃
                int bv = belong[v];
                if(bw == bv) ans[u][num[u]++] = v;
            }
            sort(ans[u],ans[u]+num[u]);
            printf("%d",num[u]);
            for(int i = 0; i < num[u]; i++)
                printf(" %d",ans[u][i]);
            puts("");
        }
    }
    return 0;
}