首页 > 代码库 > HDU 3062 Party
HDU 3062 Party
Party
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 306264-bit integer IO format: %I64d Java class name: Main
有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
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
否则输出 NO
Sample Input
2 10 1 1 1
Sample Output
YES
Source
2009 Multi-University Training Contest 16 - Host by NIT
解题:2-SAT。模板题。给每对夫妻编号为2*i 和2*i+1.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 2010;18 struct arc{19 int u,v,next;20 arc(int x = 0,int y = 0,int z = 0){21 u = x;22 v = y;23 next = z;24 }25 };26 arc e[2000100];27 int dfn[maxn],low[maxn],belong[maxn];28 bool instack[maxn];29 int head[maxn],tot,scc,index,n,m;30 stack<int>stk;31 void add(int u,int v){32 e[tot] = arc(u,v,head[u]);33 head[u] = tot++;34 }35 void tarjan(int u){36 dfn[u] = low[u] = ++index;37 instack[u] = true;38 stk.push(u);39 for(int i = head[u]; ~i; i = e[i].next){40 if(!dfn[e[i].v]){41 tarjan(e[i].v);42 if(low[e[i].v] < low[u])43 low[u] = low[e[i].v];44 }else if(instack[e[i].v] && low[u] > dfn[e[i].v])45 low[u] = dfn[e[i].v];46 }47 if(dfn[u] == low[u]){48 scc++;49 int now;50 do{51 now = stk.top();52 stk.pop();53 belong[now] = scc;54 instack[now] = false;55 }while(now != u);56 }57 58 }59 bool solve(){60 int k = n<<1;61 while(!stk.empty()) stk.pop();62 for(int i = 0; i < k; i++)63 if(!dfn[i]) tarjan(i);64 for(int i = 0; i < n; i++)65 if(belong[i<<1] == belong[i<<1|1]) return false;66 return true;67 }68 int main() {69 int u,v,x,y;70 while(~scanf("%d %d",&n,&m)){71 for(int i = 0; i < maxn; i++){72 dfn[i] = belong[i] = 0;73 head[i] = -1;74 instack[i] = false;75 }76 tot = scc = index = 0;77 for(int i = 0; i < m; i++){78 scanf("%d %d %d %d",&x,&y,&u,&v);79 x = (x<<1)+u;80 y = (y<<1)+v;81 add(x,y^1);82 add(y,x^1);83 }84 solve()?puts("YES"):puts("NO");85 }86 return 0;87 }
HDU 3062 Party
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。