首页 > 代码库 > HDU 3062 Party

HDU 3062 Party

2024-07-26 15:45:15   220人阅读

Party

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4331    Accepted Submission(s): 1415


Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
 

 

Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))

在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2 
A1,A2分别表示是夫妻的编号 
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1 
 

 

Output
如果存在一种情况 则输出YES 
否则输出 NO 
 

 

Sample Input
2 1
0 1 1 1
 

 

Sample Output
YES
 
 
 
刚看完 two set 就迫不及待想找条题来做一做 ， 这条是第一条two set的题目
题意上面已经阐述的非常清楚
 
然后做法就是把第 i 对夫妻 ， 2*i 表示为妻子， 2*i + 1 表示为丈夫  。
然后按照给出的 m 个关系连边 。
我是直接连边的 ， u -> v 这一条边表示这两个人有仇 ~  
所以在dfs的过程中 ， 如若 u 成立那么 v^1 必须成立 。
 
 
 
网上很多人是通过tarjan缩点去做 ，
如果一对夫妻在同一个强连通分量上即NO 。
应该是构图的方法不相同而已。
 
 
#include <iostream>#include <cstdio>#include <cstring>#include <stack>using namespace std;const int N = 2010;const int M = 2000010;int n , m ;int st[N] , top ;bool mark[N];int eh[N] , et[M] , nxt[M] , tot ;void init(){    tot = 0 ;    memset( eh , -1 , sizeof eh );    memset( mark , false , sizeof mark );}void addedge( int u , int v ){    et[tot] = v , nxt[tot] = eh[u] , eh[u] = tot ++ ;    et[tot] = u , nxt[tot] = eh[v] , eh[v] = tot ++ ;}bool dfs( int u ){    if( mark[u] ) return true;    if( mark[u^1] ) return false;    mark[u] = true ;    st[top++] = u ;    for( int i = eh[u] ; ~i ; i = nxt[i] ){        int v = et[i];        if( !dfs(v^1) ) return false;    }    return true;}bool solve(){    for(int i = 0 ; i < 2 * n ; i += 2 ){        if( !mark[i] && !mark[i+1] ){            top = 0 ;            if( !dfs(i) ){                while( top > 0 ) mark[ st[--top] ] = false;                if( !dfs(i+1) ) return false ;            }        }    }    return true;}int main(){    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif // LOCAL    ios::sync_with_stdio(0);    int id1 , id2 , x1 , x2 ;    while( cin >> n >> m  ){        init();        for( int i = 0 ; i < m ; ++i ){            cin >> id1 >> id2 >> x1 >> x2 ;            addedge( 2*id1 + x1 , 2*id2 + x2 );        }        if( solve() ) cout << "YES" << endl;        else cout << "NO" << endl;    }}

 

 

HDU 3062 Party


联系
我们