题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27115
思路：有一个trick要注意：当情况为 2 x y 时，可以推出当y留下时，x也必须留下。然后就是后面的k个限制关系，我们可以3^(k)次方枚举，一旦找到符合条件的就return 。然后就是反向建图，拓扑排序找可行解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
#define MAXN 2222 int n,m,k;
struct Node{
int tag;
int num[];
}node[]; vector<vector<int> >g,gg,edge; int cnt,bcc_count;
int dfn[MAXN],low[MAXN],color[MAXN];
int degree[MAXN];
bool mark[MAXN];
stack<int>S; void Tarjan(int u)
{
low[u]=dfn[u]=++cnt;
mark[u]=true;
S.push(u);
for(int i=;i<edge[u].size();i++){
int v=edge[u][i];
if(dfn[v]==){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(mark[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;
bcc_count++;
do{
v=S.top();
S.pop();
mark[v]=false;
color[v]=bcc_count;
}while(u!=v);
}
} int opp[MAXN];
bool Check()
{
for(int i=;i<=n;i++){
if(color[i]==color[i+n])return false;
opp[color[i]]=color[i+n];
opp[color[i+n]]=color[i];
}
return true;
} bool Judge()
{
int kk=(int)pow(3.0,k);
for(int i=;i<kk;i++){
for(int j=;j<=*n;j++)edge[j]=g[j];
int j=i,_count=;
while(_count<k){
int id=j%;
int x=node[_count].num[id];
if(node[_count].tag==){
edge[x+n].push_back(x);
}else
edge[x].push_back(x+n);
_count++;
j/=;
}
cnt=bcc_count=;
memset(dfn,,sizeof(dfn));
memset(mark,false,sizeof(mark));
for(int j=;j<=*n;j++)if(dfn[j]==)Tarjan(j);
if(Check())return true;
}
return false;
} int vis[MAXN];
void TopSort()
{
queue<int>que;
for(int i=;i<=bcc_count;i++){
if(degree[i]==)que.push(i);
}
memset(vis,,sizeof(vis));
while(!que.empty()){
int u=que.front();
que.pop();
if(vis[u]==){
vis[u]=;
vis[opp[u]]=-;
}
for(int i=;i<gg[u].size();i++){
int v=gg[u][i];
if(--degree[v]==)que.push(v);
}
}
} vector<int>ans;
void Solve()
{
gg.clear();
gg.resize(*n+);
memset(degree,,sizeof(degree));
for(int u=;u<=*n;u++){
for(int i=;i<edge[u].size();i++){
int v=edge[u][i];
if(color[u]!=color[v]){
gg[color[v]].push_back(color[u]);
degree[color[u]]++;
}
}
}
TopSort();
ans.clear();
for(int i=;i<=n;i++)
if(vis[color[i]]==)ans.push_back(i);
printf("%d",(int)ans.size());
for(int i=;i<(int)ans.size();i++){
printf(" %d",ans[i]);
}
puts(".");
} int main()
{
int _case,x,y,z,tag,t=;
scanf("%d",&_case);
while(_case--){
scanf("%d%d%d",&n,&m,&k);
g.clear();
g.resize(*n+);
edge.clear();
edge.resize(*n+);
while(m--){
scanf("%d%d%d",&tag,&x,&y);
if(tag==)g[x+n].push_back(y),g[y+n].push_back(x);
else if(tag==)g[x+n].push_back(y+n),g[y].push_back(x);
else if(tag==)g[x].push_back(y+n),g[y].push_back(x+n);
else g[x].push_back(y+n),g[y].push_back(x+n),g[x+n].push_back(y),g[y+n].push_back(x);
}
for(int i=;i<k;i++){
scanf("%d%d%d%d",&node[i].tag,&node[i].num[],&node[i].num[],&node[i].num[]);
}
printf("Case %d: ",t++);
if(Judge()){
printf("Possible ");
Solve();
}else
puts("Impossible.");
}
return ;
}