【图论】2018国庆三校联考D5T2

分析：

题意非常丑陋。。。简化出来就一句话：每个点有选中、未选中两种状态，现在给出一些矛盾关系，要求加入尽可能少的矛盾关系，使得没有合法方案。

如此2sat的模型，显然需要2sat的连边方式。。。然后直接枚举每个位置选、不选是否合法即可。若不选合法，则考虑其练的边是否有一个选择的点，如果有则可以用1的代价使得这个点不选非法。具体的情况见代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 4010
using namespace std;
struct node{
	int x;
	node *nxt;	
}edge[MAXN*4];
node *head[MAXN],*ncnt=edge;
int n,m;
void add_edge(int u,int v){
	ncnt++;
	ncnt->x=v;
	ncnt->nxt=head[u];
	head[u]=ncnt;
}
bool vis[MAXN];
void dfs(int x){
	vis[x]=1;
	for(node *v=head[x];v!=NULL;v=v->nxt){
		int u=v->x;
		if(vis[u]==0)
			dfs(u);
	}
}
int query(int x){
	memset(vis,0,sizeof vis);
	dfs(x);	
	for(int i=1;i<=n;i++)
		if(vis[i]==1&&vis[i+n]==1)
			return 0;
	return 1;
}
int check(){
	for(int i=1;i<=n;i++)
		if(vis[i]==1)
			return 1;
	return 0;	
}
int l[MAXN];
int main(){
	freopen("god.in","r",stdin);
	freopen("god.out","w",stdout);
	int t;
	SF("%d",&t);
	while(t--){
		SF("%d%d",&n,&m);
		for(int i=1;i<=n*2;i++)
			head[i]=NULL;
		ncnt=edge;
		int ans=3,u,v;
		for(int i=1;i<=m;i++){
			SF("%d%d",&u,&v);
			if(u<0)
				u=-u+n;
			if(v<0)
				v=-v+n;
			add_edge(u,(v+n)%(2*n));
			add_edge(v,(u+n)%(2*n));
		}
		for(int i=1;i<=n;i++){
			int res1=query(i);
			int res2=query(i+n);
			int con=check();
			if(res2==0)
				ans=min(ans,res1);
			else if(con==1)
				ans=min(ans,1+res1);
		}
		if(ans==3)
			PF("No Way\n");	
		else
			PF("%d\n",ans);
	}
}