HDU 1824 Let's go home （2-SAT判断）-白红宇

HDU 1824 Let's go home （2-SAT判断）

阅读量：4072 次

发布时间：2019-05-25

本文共 1265 字，大约阅读时间需要 4 分钟。

题目链接：

【题目】

Problem Description

小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。

—— 余光中

集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。

Input

第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。

接下来有T行，每行三个整数，表示一个队的队员编号，第一个队员就是该队队长。

然后有M行，每行两个整数，表示一对队员的编号。

每个队员只属于一个队。队员编号从0开始。

Output

可行输出yes，否则输出no，以EOF为结束。

Sample Input

1 20 1 20 11 22 40 1 23 4 50 30 41 31 4

Sample Output

yesno

【思路】

每一个队伍中，要么队长留下，要么另外两个队员留下，这是一个矛盾对，可以把队长看成一个点，把两个队员也抽象成一个点，

把他们进行一个映射, 对于a，b，c， !a->b, !b->a, !c->a，即f[a] = b, f[b]=a, f[c]=a，然后直接用2-SAT判断即可。

【代码】

#include
    
      #include
     
      #include
      
       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

转载地址：http://upzni.baihongyu.com/

你可能感兴趣的文章