POJ 1904 HDU 4685 - c++编程基础

TOP

POJ 1904 HDU 4685

2014-11-23 19:05:25 来源: 作者: 【大中小】浏览:5次

Tags：POJ 1904 HDU 4685

这两道题差不多，POJ这道我很久以前就做过，但是比赛的时候居然没想起来。。

POJ 这道题的题意是，N个王子每个人都有喜欢的公主，当他们选定一个公主结婚时，必须是的剩下的人也能找到他喜欢的公主结婚。

思路，首先对于王子，对于每一个他喜欢的公主，直接连边，然后再根据已经给出的匹配方案，建立公主->王子的边。

最后求出SCC后在同一强联通分量里的王子和公主就可以了。

代码就不贴了

下面再讲一下HDU 4685这道题，两道题的唯一区别就是，上一道题，每个公主到王子的匹配方案都是给出的，是一定存在的，那是因为公主和王子的个数是相同的。

但是这道题公主和王子的个数不同，就无法做到两两匹配，必然存在光棍的情况。

光棍其实挺正常的，但是对于这道题，我们就需要虚拟一些王子和公主出来。

一个王子没有匹配的话，那么虚拟一个公主出来，表示所有的王子都喜欢这个公主，同理虚拟出王子的情况。

那么在求出匹配之后，我们就可以根据这些匹配来建立公主->王子的边，然后操作就和上一题一样了。

代码：

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#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   
#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] ;  
vectorG[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) ;  
        setfk ;  
        __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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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
#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] ;
vectorG[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) ;
        setfk ;
        __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 ;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1022 Train Problem I	下一篇：POJ 3254 Corn Fields

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: