POJ 1904 HDU 4685

這兩道題差不多，POJ這道我很久以前就做過，但是比賽的時候居然沒想起來。。

POJ 這道題的題意是，N個王子每個人都有喜歡的公主，當他們選定一個公主結婚時，必須是的剩下的人也能找到他喜歡的公主結婚。

思路，首先對於王子，對於每一個他喜歡的公主，直接連邊，然後再根據已經給出的匹配方案，建立公主->王子的邊。

最後求出SCC後在同一強聯通分量裡的王子和公主就可以了。

代碼就不貼了

下面再講一下HDU 4685這道題，兩道題的唯一區別就是，上一道題，每個公主到王子的匹配方案都是給出的，是一定存在的，那是因為公主和王子的個數是相同的。

但是這道題公主和王子的個數不同，就無法做到兩兩匹配，必然存在光棍的情況。

光棍其實挺正常的，但是對於這道題，我們就需要虛擬一些王子和公主出來。

一個王子沒有匹配的話，那麼虛擬一個公主出來，表示所有的王子都喜歡這個公主，同理虛擬出王子的情況。

那麼在求出匹配之後，我們就可以根據這些匹配來建立公主->王子的邊，然後操作就和上一題一樣了。

代碼：

#include <set>   
#include <map>   
#include <stack>   
#include <cmath>   
#include <queue>   
#include <cstdio>   
#include <string>   
#include <vector>   
#include <iomanip>   
#include <cstring>   
#include <iostream>   
#include <algorithm>   
#include <ctime>   
#define Max 2505   
#define FI first   
#define SE second   
#define ll long long   
#define PI acos(-1.0)   
#define inf 0x3fffffff   
#define LL(x) ( x << 1 )   
#define bug puts("here")   
#define PII pair<int,int>   
#define RR(x) ( x << 1 | 1 )   
#define mp(a,b) make_pair(a,b)   
#define mem(a,b) memset(a,b,sizeof(a))   
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )   
  
using namespace std;  
  
  
inline void RD(int &ret) {  
    char c;  
    int flag = 1 ;  
    do {  
        c = getchar();  
        if(c == '-')flag = -1 ;  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
    ret *= flag ;  
}  
  
inline void OT(int a) {  
    if(a >= 10)OT(a / 10) ;  
    putchar(a % 10 + '0') ;  
}  
  
inline void OT(double a) {  
    char x[111] ;  
    sprintf(x , "%f" , a) ;  
    printf("%s\n",x) ;  
}  
inline void RD(double &ret) {  
    char c ;  
    int flag = 1 ;  
    do {  
        c = getchar() ;  
        if(c == '-')flag = -1 ;  
    } while(c < '0' || c > '9') ;  
    ll fuck1 = c - '0' ;  
    while((c = getchar()) >= '0' && c <= '9') {  
        fuck1 = fuck1 * 10 + c - '0' ;  
    }  
    ll fuck2 = 1 ;  
    while((c = getchar()) >= '0' && c <= '9') {  
        fuck1 = fuck1 * 10 + c - '0' ;  
        fuck2 *= 10 ;  
    }  
    ret = flag * (double)fuck1 / (double)(fuck2) ;  
}  
/***************************************************/  
#define N 2005   
int n , m ;  
int fk[N] ;  
int vis[N] ;  
struct kdq {  
    int s , e , next ;  
} ed[N * N] ;  
int head[N] , num = 0 ;  
int nn ;  
int linkx[N] ,linky[N] ;  
vector<int>G[N] ;  
void add(int s ,int e) {  
    ed[num].s = s ;  
    ed[num].e = e ;  
    ed[num].next = head[s] ;  
    head[s] = num ++ ;  
}  
  
int dfs(int now) {  
    int sz = G[now].size() ;  
    for (int i = 0 ; i < sz ; i ++ ) {  
        int e = G[now][i] ;  
        if(!vis[e]) {  
            vis[e] = 1 ;  
            if(linky[e] == -1 || dfs(linky[e])) {  
                linky[e] = now ;  
                linkx[now] = e ;  
                return 1 ;  
            }  
        }  
    }  
    return 0 ;  
}  
  
  
//tarjan_define   
int low[N] , dfn[N] , st[N] , belong[N] ;  
int top , dp ,SCC ;  
  
void tarjan(int now) {  
    vis[now] = 1 ;  
    st[top ++ ] = now ;  
    dfn[now] = low[now] = dp ++ ;  
    for (int i = head[now] ; i != -1 ; i = ed[i].next ) {  
        int v = ed[i].e ;  
        if(dfn[v] == -1) {  
            tarjan(v) ;  
            low[now] = min(low[now] ,low[v]) ;  
        } else if(vis[v]) {  
            low[now] = min(low[now] ,dfn[v]) ;  
        }  
    }  
    if(low[now] == dfn[now]) {  
        int xx ;  
        SCC ++ ;  
        do {  
            xx = st[-- top ] ;  
            vis[xx] = 0 ;  
            belong[xx] = SCC ;  
        } while(xx != now) ;  
    }  
}  
  
//init   
void init() {  
    mem(linkx ,-1) ;  
    mem(linky ,-1) ;  
    mem(vis, 0) ;  
    mem(low,0) ;  
    mem(dfn ,-1) ;  
    mem(st ,0) ;  
    mem(head ,-1) ;  
    num = top = dp = SCC = 0 ;  
}  
int main() {  
    int T ;  
#ifndef ONLINE_JUDGE   
    freopen("D:\\fuck.txt","r",stdin) ;  
#endif   
    cin >> T ;  
    int ca = 0 ;  
    while(T -- ) {  
        RD(n) ;  
        RD(m) ;  
        int nfk = max(m , n) ;  
        init() ;  
        for (int i = 0 ; i <= N >> 1 ; i ++ ) {  
            G[i].clear() ;  
        }  
  
        REP(i , 1 , n ) {  
            int x ;  
            RD(x) ;  
            while(x -- ) {  
                int y ;  
                RD(y) ;  
                add(i , nfk + y) ;  
                G[i].push_back(nfk + y) ;  
            }  
        }  
        nn = 0 ;  
        for (int i = 1 ; i <= nfk ; i ++ ) {  
            mem(vis ,0) ;  
            nn += dfs(i) ;  
        }  
        nn = 2 * nfk ;  
        for (int i = 1 ; i <= nfk ; i ++ ) { //虛擬公主   
            if(linkx[i] == -1) {  
                linkx[i] = ++ nn ;  
                linky[nn] = i ;  
                for (int j = 1 ; j <= nfk ; j ++ ) { //所有王子都喜歡這個公主   
                    add(j , nn) ;  
                }  
            }  
            add(linkx[i] , i) ;  
        }  
        for (int i = nfk + 1 ; i <= nfk << 1 ; i ++ ) { //虛擬王子   
            if(linky[i] == -1) {  
                linkx[++ nn] = i ;  
                linky[i] = nn ;  
                for (int j = nfk + 1 ; j <= nfk + nfk ; j ++ ) { //這個王子喜歡所有公主   
                    add(nn , j) ;  
                }  
            }  
            add(i , linky[i]) ;  
        }  
        mem(vis, 0) ;  
        for (int i = 1 ; i <= nn ; i ++ ) {  
            if(dfn[i] == -1)tarjan(i) ;  
        }  
        printf("Case #%d:\n",++ ca) ;  
        set<int>fk ;  
        __typeof(fk.begin()) it ;  
        for (int i = 1 ; i <= n ; i ++ ) {  
            fk.clear() ;  
            for (int j = head[i] ; ~j ; j = ed[j].next ) {  
                int x = belong[i] ;  
                int y = belong[ed[j].e] ;  
                if(x == y && ed[j].e <= nfk + m) {  
                    fk.insert(ed[j].e - nfk) ;  
                }  
            }  
            printf("%d",fk.size()) ;  
            for (it = fk.begin() ; it != fk.end() ; it ++) {  
                printf(" %d",*it) ;  
            }  
            puts("") ;  
        }  
    }  
    return 0 ;  
}  

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

using namespace std;


inline void RD(int &ret) {
    char c;
    int flag = 1 ;
    do {
        c = getchar();
        if(c == '-')flag = -1 ;
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
    ret *= flag ;
}

inline void OT(int a) {
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}

inline void OT(double a) {
    char x[111] ;
    sprintf(x , "%f" , a) ;
    printf("%s\n",x) ;
}
inline void RD(double &ret) {
    char c ;
    int flag = 1 ;
    do {
        c = getchar() ;
        if(c == '-')flag = -1 ;
    } while(c < '0' || c > '9') ;
    ll fuck1 = c - '0' ;
    while((c = getchar()) >= '0' && c <= '9') {
        fuck1 = fuck1 * 10 + c - '0' ;
    }
    ll fuck2 = 1 ;
    while((c = getchar()) >= '0' && c <= '9') {
        fuck1 = fuck1 * 10 + c - '0' ;
        fuck2 *= 10 ;
    }
    ret = flag * (double)fuck1 / (double)(fuck2) ;
}
/***************************************************/
#define N 2005
int n , m ;
int fk[N] ;
int vis[N] ;
struct kdq {
    int s , e , next ;
} ed[N * N] ;
int head[N] , num = 0 ;
int nn ;
int linkx[N] ,linky[N] ;
vector<int>G[N] ;
void add(int s ,int e) {
    ed[num].s = s ;
    ed[num].e = e ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}

int dfs(int now) {
    int sz = G[now].size() ;
    for (int i = 0 ; i < sz ; i ++ ) {
        int e = G[now][i] ;
        if(!vis[e]) {
            vis[e] = 1 ;
            if(linky[e] == -1 || dfs(linky[e])) {
                linky[e] = now ;
                linkx[now] = e ;
                return 1 ;
            }
        }
    }
    return 0 ;
}


//tarjan_define
int low[N] , dfn[N] , st[N] , belong[N] ;
int top , dp ,SCC ;

void tarjan(int now) {
    vis[now] = 1 ;
    st[top ++ ] = now ;
    dfn[now] = low[now] = dp ++ ;
    for (int i = head[now] ; i != -1 ; i = ed[i].next ) {
        int v = ed[i].e ;
        if(dfn[v] == -1) {
            tarjan(v) ;
            low[now] = min(low[now] ,low[v]) ;
        } else if(vis[v]) {
            low[now] = min(low[now] ,dfn[v]) ;
        }
    }
    if(low[now] == dfn[now]) {
        int xx ;
        SCC ++ ;
        do {
            xx = st[-- top ] ;
            vis[xx] = 0 ;
            belong[xx] = SCC ;
        } while(xx != now) ;
    }
}

//init
void init() {
    mem(linkx ,-1) ;
    mem(linky ,-1) ;
    mem(vis, 0) ;
    mem(low,0) ;
    mem(dfn ,-1) ;
    mem(st ,0) ;
    mem(head ,-1) ;
    num = top = dp = SCC = 0 ;
}
int main() {
    int T ;
#ifndef ONLINE_JUDGE
    freopen("D:\\fuck.txt","r",stdin) ;
#endif
    cin >> T ;
    int ca = 0 ;
    while(T -- ) {
        RD(n) ;
        RD(m) ;
        int nfk = max(m , n) ;
        init() ;
        for (int i = 0 ; i <= N >> 1 ; i ++ ) {
            G[i].clear() ;
        }

        REP(i , 1 , n ) {
            int x ;
            RD(x) ;
            while(x -- ) {
                int y ;
                RD(y) ;
                add(i , nfk + y) ;
                G[i].push_back(nfk + y) ;
            }
        }
        nn = 0 ;
        for (int i = 1 ; i <= nfk ; i ++ ) {
            mem(vis ,0) ;
            nn += dfs(i) ;
        }
        nn = 2 * nfk ;
        for (int i = 1 ; i <= nfk ; i ++ ) { //虛擬公主
            if(linkx[i] == -1) {
                linkx[i] = ++ nn ;
                linky[nn] = i ;
                for (int j = 1 ; j <= nfk ; j ++ ) { //所有王子都喜歡這個公主
                    add(j , nn) ;
                }
            }
            add(linkx[i] , i) ;
        }
        for (int i = nfk + 1 ; i <= nfk << 1 ; i ++ ) { //虛擬王子
            if(linky[i] == -1) {
                linkx[++ nn] = i ;
                linky[i] = nn ;
                for (int j = nfk + 1 ; j <= nfk + nfk ; j ++ ) { //這個王子喜歡所有公主
                    add(nn , j) ;
                }
            }
            add(i , linky[i]) ;
        }
        mem(vis, 0) ;
        for (int i = 1 ; i <= nn ; i ++ ) {
            if(dfn[i] == -1)tarjan(i) ;
        }
        printf("Case #%d:\n",++ ca) ;
        set<int>fk ;
        __typeof(fk.begin()) it ;
        for (int i = 1 ; i <= n ; i ++ ) {
            fk.clear() ;
            for (int j = head[i] ; ~j ; j = ed[j].next ) {
                int x = belong[i] ;
                int y = belong[ed[j].e] ;
                if(x == y && ed[j].e <= nfk + m) {
                    fk.insert(ed[j].e - nfk) ;
                }
            }
            printf("%d",fk.size()) ;
            for (it = fk.begin() ; it != fk.end() ; it ++) {
                printf(" %d",*it) ;
            }
            puts("") ;
        }
    }
    return 0 ;
}