图论--2-SAT--Ligthoj 1407 Explosion 三元关系枚举

Planet Krypton is about to explode. The inhabitants of this planet have to leave the planet immediately. But the problem is that, still some decisions have to be made - where to go, how to go etc. So, the council of Krypton has invited some of the people to meet in a large hall.

There are n people in planet Krypton, for simplicity they are given ids from 1 to n. The council uses a super computer named Oracle to call them in the meeting. Oracle has four types of messages for invitation. The message format is type x y, where x and y are two different person's ids and type is an integer as follows:

1. 1 x y means that either x or y should be present in the meeting.

2. 2 x y means that if x is present, then no condition on y, but if x is absent y should be absent

3. 3 x y means that either x or y must be absent.

4. 4 x y means that either x or y must be present but not both.

Each member of the council has an opinion too. The message format is type x y z, where x, y and z are three different person's ids and type is an integer as follows:

1. 1 x y z means that at least one of x, y or z should be present

2. 2 x y z means that at least one of x, y or z should be absent

Now you have to find whether the members can be invited such that every message by oracle and the council members are satisfied.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers n, m and k (3 ≤ n ≤ 1000, 0 ≤ m ≤ 2000, 0 ≤ k ≤ 5) where m means the number of messages by oracle, k means the total members in the council. Each of the next m lines will contain a message of Oracle in the format given above. Each of the next k lines will contain a message of a council member. You can assume that all the ids given are correct.

Output

For each case, print the case number and whether it's possible to invite the people such that all the messages are satisfied. If it's not possible, then print'Impossible.' in a single line. Otherwise, print 'Possible' and the number of invited people and the ids of the invited people in ascending order. Print the line leaving a single space between fields. Terminate this line with a '.'. See the samples for more details. There can be multiple answers; print any valid one.

Sample Input

Output for Sample Input

3

3 2 1

1 2 3

1 1 2 3

4 4 1

2 2 1

4 1 2

4 1 3

4 1 4

2 2 3 4

4 5 0

3 1 2

2 2 3

2 2 4

2 1 2

2 2 1

Case 1: Possible 2 1 3.

Case 2: Impossible.

Case 3: Possible 0.

Note

This is a special judge problem; wrong output format may cause 'Wrong Answer'.

题目大意：

有一个机器产生m个限制，限制有4种：

1. x or y 至少有1个人参加

2. x不参加则 y必须不参加，（隐含 y参加 x必须参加）

3. x or y 至少有1个人不参加

4. x & y 同时参加或者不参加

有 k 个人进行投票，有2种类别

1. x y z 至少有一个人参加

2. x y z 至少有一个人不参加

有n 个人参加会议，m 个机器限制，k个人投票 (3 ≤ n ≤ 1000, 0 ≤ m ≤ 2000, 0 ≤ k ≤ 5)

解题思路：肯定是 2-sat，k比较小直接枚举3^k。剩下的就是一个模板。

建图：

二元关系直接建图，三元关系枚举成二元判断是否可行，不可行，继续枚举，可行输出答案，知道都枚举完，就无解。反正是一个NP完全问题，所以枚举无伤大雅。二元建图，看我博客2-SAT详解，一看就明白。戳死我

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define MAXN 2000+100

#define MAXM 10000+100

using namespace std;

struct Edge

{

    int from, to, next;

};

Edge edge[MAXM], Redge[MAXM];

int head[MAXN], edgenum;

int Rhead[MAXN], Redgenum;//这些数组用于copy 这样就不用再次建已经确定的边了

struct Node

{

    int op, x, y, z;

};

Node num[5];

int low[MAXN], dfn[MAXN];

int sccno[MAXN], scc_cnt;

int dfs_clock;

stack<int> S;

bool Instack[MAXN];

int N, M, K;

void init()

{

    edgenum = 0;

    memset(head, -1, sizeof(head));

}

void addEdge(int u, int v)

{

    Edge E = {u, v, head[u]};

    edge[edgenum] = E;

    head[u] = edgenum++;

}

void input()

{

    int x, y, z, op;

    while(M--)

    {

        scanf("%d%d%d", &op, &x, &y);

        if(op == 1)//x和y至少去一个

        {

            addEdge(y + N, x);//y不去x去

            addEdge(x + N, y);//x不去y去

        }

        else if(op == 2)

        {

            addEdge(y, x);//注意 若y去则x是一定去的

            addEdge(x + N, y + N);//x不去y也不去

        }

        else if(op == 3)//x和y至少一个不去

        {

            addEdge(x, y + N);//x去 y不去

            addEdge(y, x + N);//y去 x不去

        }

        else//两个人只能去一个

        {

            addEdge(x, y + N);

            addEdge(y, x + N);

            addEdge(x + N, y);

            addEdge(y + N, x);

        }

    }

    for(int i = 0; i < K; i++)

        scanf("%d%d%d%d", &num[i].op, &num[i].x, &num[i].y, &num[i].z);

    memcpy(Rhead, head, sizeof(head));

    memcpy(Redge, edge, sizeof(edge));

    Redgenum = edgenum;

}

void tarjan(int u, int fa)

{

    int v;

    low[u] = dfn[u] = ++dfs_clock;

    S.push(u);

    Instack[u] = true;

    for(int i = head[u]; i != -1; i = edge[i].next)

    {

        v = edge[i].to;

        if(!dfn[v])

        {

            tarjan(v, u);

            low[u] = min(low[u], low[v]);

        }

        else if(Instack[v])

            low[u] = min(low[u], dfn[v]);

    }

    if(low[u] == dfn[u])

    {

        scc_cnt++;

        for(;;)

        {

            v = S.top(); S.pop();

            Instack[v] = false;

            sccno[v] = scc_cnt;

            if(v == u) break;

        }

    }

}

void find_cut(int l, int r)

{

    memset(low, 0, sizeof(low));

    memset(dfn, 0, sizeof(dfn));

    memset(sccno, 0, sizeof(sccno));

    memset(Instack, false, sizeof(Instack));

    dfs_clock = scc_cnt = 0;

    for(int i = l; i <= r; i++)

        if(!dfn[i]) tarjan(i, -1);

}

int fp[MAXN];//建立SCC间的映射

bool two_sat()//判断当前情况是否成立

{

    find_cut(1, 2*N);

    for(int i = 1; i <= N; i++)

    {

        if(sccno[i] == sccno[i+N])

            return false;

        else

        {

            fp[sccno[i]] = sccno[i+N];

            fp[sccno[i+N]] = sccno[i];

        }

    }

    return true;

}

int k = 1;

vector<int> G[MAXN];//缩点后新图

int in[MAXN];//记录SCC入度

void suodian()//缩点

{

    for(int i = 1; i <= scc_cnt; i++) G[i].clear(), in[i] = 0;

    for(int i = 0; i < edgenum; i++)

    {

        int u = sccno[edge[i].from];

        int v = sccno[edge[i].to];

        if(u != v)

            G[v].push_back(u), in[u]++;

    }

}

int color[MAXN];//染色

void toposort()//拓扑染色

{

    queue<int> Q;

    memset(color, -1, sizeof(color));

    for(int i = 1; i <= scc_cnt; i++) if(in[i] == 0) Q.push(i);

    while(!Q.empty())

    {

        int u = Q.front();

        Q.pop();

        if(color[u] == -1)

        {

            color[u] = 1;

            color[fp[u]] = 0;

        }

        for(int i = 0; i < G[u].size(); i++)

        {

            int v = G[u][i];

            if(--in[v] == 0)

                Q.push(v);

        }

    }

}

void solve()

{

    int State = (int)pow(3, K);//总状态数

    bool flag = false;

    for(int S = 0; S < State; S++)//这里状态下标从1开始或从2开始 都不会影响 注意取值就行了

    {

        memcpy(head, Rhead, sizeof(Rhead));//还原数组

        memcpy(edge, Redge, sizeof(Redge));

        edgenum = Redgenum;

        int T = S;

        for(int i = 0; i < K; i++)//继续枚举状态建图

        {

            int s;

            switch(T % 3)//需要仔细琢磨 这个过程

            {

                case 0: s = num[i].x; break;

                case 1: s = num[i].y; break;

                case 2: s = num[i].z; break;

            }

            T /= 3;

            if(num[i].op == 1)

                addEdge(s + N, s);//s一定去

            else

                addEdge(s, s + N);//s一定不去

        }

        if(two_sat())//成立

        {

            flag = true;

            break;

        }

    }

    printf("Case %d: ", k++);

    if(!flag)

    {

        printf("Impossible.\n");

        return ;

    }

    printf("Possible");

    //输出可行解

    suodian();

    toposort();

    int ans = 0;

    for(int i = 1; i <= N; i++)

    {

        if(color[sccno[i]] == 1)

            ans++;

    }

    printf(" %d", ans);

    for(int i = 1; i <= N; i++)

        if(color[sccno[i]] == 1)

            printf(" %d", i);

    printf(".\n");

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%d%d", &N, &M, &K);

        init();

        input();

        solve();

    }

    return 0;

}

巴特西

图论--2-SAT--Ligthoj 1407 Explosion 三元关系枚举

最新文章

热门文章