1407 - Explosion
 | PDF (English) | Statistics | Forum |
| Time Limit: 3 second(s) | Memory Limit: 32 MB |
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 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'.
PROBLEM SETTER: JANE ALAM JAN SPECIAL THANKS: DEREK KISMAN
題意：要從N個人（編号從1到N）裡面選一些人參加會議，先給出M個2布爾變量的限制條件和K個3布爾變量的限制條件。讓你選出若幹個人參加會議，若不存在方案輸出Impossible。否則輸出Possible并且在後面輸出參加會議的人數以及他們的編号（編号從小到大）。
2布爾變量限制如下
1，x y 表示x和y至少去一個 2，x y 表示 x去的話y怎麼樣都可以，但是若x不去那麼y一定不去 3，x y 表示x和y至少一個不去 4，x y 表示x和y必須去一個且隻能去一個
3布爾變量限制如下
1，x y z 表示x、y和z至少去一個 2，x y z 表示x、y和z至少一個不去
快一天了，╮(╯▽╰)╭。還沒有做過帶有3個布爾變量的題目，一開始天真的用2-sat思維做，結果WA到死。。。最後發現K值最多為5，還能怎樣？直接暴力枚舉所有狀态吧。幾個小時沒白過，至少學會了處理3個布爾變量的情況。 O(∩_∩)O~~
這裡隻說一下2布爾變量的建圖
1，x y 表示x和y至少去一個 addEdge(y + N, x); //y不去x去
addEdge(x + N, y);//x不去y去
2，x y 表示 x去的話y怎麼樣都可以，但是若x不去那麼y一定不去 addEdge(y, x); //注意 若y去則x是一定去的
addEdge(x + N, y + N); //x不去y也不去
3，x y 表示x和y至少一個不去 addEdge(x, y + N); //x去 y不去
addEdge(y, x + N);//y去 x不去
4，x y 表示x和y必須去一個且隻能去一個 addEdge(x, y + N);
addEdge(y, x + N);
addEdge(x + N, y);
addEdge(y + N, x);
至于3 個布爾變量狀态的枚舉，強烈建議模拟一下，真的不好講。畢竟我也是初學3布爾變量的渣渣，o(╯□╰)o
AC代碼：
#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;
}