题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1824
【题目】
Problem Description
小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。
—— 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
—— 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
Input
第一行有两个整数,T和M,1<=T<=1000表示队伍数,1<=M<=5000表示对数。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
Output
可行输出yes,否则输出no,以EOF为结束。
Sample Input
1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4
Sample Output
yes no
【思路】
每一个队伍中,要么队长留下,要么另外两个队员留下,这是一个矛盾对,可以把队长看成一个点,把两个队员也抽象成一个点,
把他们进行一个映射, 对于a,b,c, !a->b, !b->a, !c->a, 即f[a] = b, f[b]=a, f[c]=a,然后直接用2-SAT判断即可。
【代码】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long int64; const int MAXN = 3010; const int VN = MAXN*2; const int EN = VN*2; int t, m; int f[MAXN]; struct Edge{ int v, next; }; struct Graph{ public: void init(){ size = 0; memset(head, -1, sizeof(head)); } void addEdge(int u, int v){ E[size].v = v; E[size].next = head[u]; head[u] = size++; } public: int head[VN]; Edge E[EN]; private: int size; }g; class Tow_Sat{ public: bool check(const Graph&g, const int n){ scc(g, n); for(int i=0; i<n; ++i) if(belong[3*i] == belong[f[3*i]] || belong[3*i+1] == belong[f[3*i+1]]) return false; return true; } private: int top, bcnt, idx; int DFN[VN]; int low[VN]; int belong[VN]; int sta[VN]; bool inStack[VN]; void targan(const Graph&g, const int u){ int v; DFN[u] = low[u] = ++idx; sta[top++] = u; inStack[u] = true; for(int e=g.head[u]; e!=-1; e=g.E[e].next){ v = g.E[e].v; if(DFN[v] < 0){ targan(g, v); low[u] = min(low[u], low[v]); }else if(inStack[v]){ low[u] = min(low[u], DFN[v]); } } if(DFN[u] == low[u]){ ++bcnt; do{ v = sta[--top]; inStack[v] = false; belong[v] = bcnt; }while(u != v); } } void scc(const Graph&g, int n){ top = bcnt = idx = 0; memset(DFN, -1, sizeof(DFN)); memset(inStack, 0, sizeof(inStack)); for(int i=0; i<3*n; ++i) if(DFN[i] < 0) targan(g, i); } }sat; int main(){ int a,b,c; while(~scanf("%d%d", &t, &m)){ g.init(); for(int i=0; i<t; ++i){ scanf("%d%d%d", &a,&b,&c); g.addEdge(b, c); g.addEdge(c, b); f[a] = b; f[b] = f[c] = a; } bool flag = true; for(int i=0; i<m; ++i){ scanf("%d%d", &a,&b); g.addEdge(a, f[b]); g.addEdge(b, f[a]); } if(flag && sat.check(g, t)) puts("yes"); else puts("no"); } return 0; }
有疑问加站长微信联系(非本文作者)