【2-SAT问题】
现有一个由N个布尔值组成的序列A,给出一些限制关系,比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等,要确定A[0..N-1]的值,使得其满足所有限制关系。这个称为SAT问题,特别的,若每种限制关系中最多只对两个元素进行限制,则称为2-SAT问题。
由于在2-SAT问题中,最多只对两个元素进行限制,所以可能的限制关系共有11种:
A[x]
NOT A[x]
A[x] AND A[y]
A[x] AND NOT A[y]
A[x] OR A[y]
A[x] OR NOT A[y]
NOT (A[x] AND A[y])
NOT (A[x] OR A[y])
A[x] XOR A[y]
NOT (A[x] XOR A[y])
A[x] XOR NOT A[y]
进一步,A[x] AND A[y]相当于(A[x]) AND (A[y])(也就是可以拆分成A[x]与A[y]两个限制关系),NOT(A[x] OR A[y])相当于NOT A[x] AND NOT A[y](也就是可以拆分成NOT A[x]与NOT A[y]两个限制关系)。因此,可能的限制关系最多只有9种。
在实际问题中,2-SAT问题在大多数时候表现成以下形式:有N对物品,每对物品中必须选取一个,也只能选取一个,并且它们之间存在某些限制关系(如某两个物品不能都选,某两个物品不能都不选,某两个物品必须且只能选一个,某个物品必选)等,这时,可以将每对物品当成一个布尔值(选取第一个物品相当于0,选取第二个相当于1),如果所有的限制关系最多只对两个物品进行限制,则它们都可以转化成9种基本限制关系,从而转化为2-SAT模型。
【建模】
其实2-SAT问题的建模是和实际问题非常相似的。
建立一个2N阶的有向图,其中的点分为N对,每对点表示布尔序列A的一个元素的0、1取值(以下将代表A[i]的0取值的点称为i,代表A[i]的1取值的点称为i')。显然每对点必须且只能选取一个。然后,图中的边具有特定含义。若图中存在边,则表示若选了i必须选j。可以发现,上面的9种限制关系中,后7种二元限制关系都可以用连边实现,比如NOT(A[x] AND A[y])需要连两条边
【O(NM)算法:求字典序最小的解】
根据2-SAT建成的图中边的定义可以发现,若图中i到j有路径,则若i选,则j也要选;或者说,若j不选,则i也不能选;
因此得到一个很直观的算法:
(1)给每个点设置一个状态V,V=0表示未确定,V=1表示确定选取,V=2表示确定不选取。称一个点是已确定的当且仅当其V值非0。设立两个队列Q1和Q2,分别存放本次尝试选取的点的编号和尝试不选的点的编号。
(2)若图中所有的点均已确定,则找到一组解,结束,否则,将Q1、Q2清空,并任选一个未确定的点i,将i加入队列Q1,将i'加入队列Q2;
(3)找到i的所有后继。对于后继j,若j未确定,则将j加入队列Q1;若j'(这里的j'是指与j在同一对的另一个点)未确定,则将j'加入队列Q2;
(4)遍历Q2中的每个点,找到该点的所有前趋(这里需要先建一个补图),若该前趋未确定,则将其加入队列Q2;
(5)在(3)(4)步操作中,出现以下情况之一,则本次尝试失败,否则本次尝试成功:
<1>某个已被加入队列Q1的点被加入队列Q2;
<2>某个已被加入队列Q2的点被加入队列Q1;
<3>某个j的状态为2;
<4>某个i'或j'的状态为1或某个i'或j'的前趋的状态为1;
(6)若本次尝试成功,则将Q1中的所有点的状态改为1,将Q2中所有点的状态改为2,转(2),否则尝试点i',若仍失败则问题无解。
该算法的时间复杂度为O(NM)(最坏情况下要尝试所有的点,每次尝试要遍历所有的边),但是在多数情况下,远远达不到这个上界。
具体实现时,可以用一个数组vst来表示队列Q1和Q2。设立两个标志变量i1和i2(要求对于不同的i,i1和i2均不同,这样可以避免每次尝试都要初始化一次,节省时间),若vst[i]=i1则表示i已被加入Q1,若vst[i]=i2则表示i已被加入Q2。不过Q1和Q2仍然是要设立的,因为遍历(BFS)的时候需要队列,为了防止重复遍历,加入Q1(或Q2)中的点的vst值必然不等于i1(或i2)。中间一旦发生矛盾,立即中止尝试,宣告失败。
该算法虽然在多数情况下时间复杂度到不了O(NM),但是综合性能仍然不如下面的O(M)算法。不过,该算法有一个很重要的用处:求字典序最小的解!
如果原图中的同一对点编号都是连续的(01、23、45……)则可以依次尝试第0对、第1对……点,每对点中先尝试编号小的,若失败再尝试编号大的。这样一定能求出字典序最小的解(如果有解的话),因为一个点一旦被确定,则不可更改。
如果原图中的同一对点编号不连续(比如03、25、14……)则按照该对点中编号小的点的编号递增顺序将每对点排序,然后依次扫描排序后的每对点,先尝试其编号小的点,若成功则将这个点选上,否则尝试编号大的点,若成功则选上,否则(都失败)无解。
2-sat构图进行可行性判断问题。二分+2-sat求解。
解题报告here
HDU 3622
/*
HDU 3622
题意:给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),
每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸
的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相
交(可以相切),求解这个最大半径.
首先二分最大半径值,然后2-sat构图判断其可行性,对于每
两队位置(u,uu)和(v,vv),如果u和v之间的距离小于2*id,也就
是说位置u和位置v处不能同时防止炸弹(两范围相交),所以连边(u,vv)
和(v,uu),求解强连通分量判断可行性.
注意精度问题
*/
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std;
const int MAXN=210;
const int MAXM=40005;//边的最大数
const double eps=1e-5;
struct Edge
{
int to,next;
}edge1[MAXM],edge2[MAXM];
int head1[MAXN];
int head2[MAXN];
int tol1,tol2;
bool vis1[MAXN],vis2[MAXN];
int Belong[MAXN];//连通分量标记
int T[MAXN];//dfs结点结束时间
int Bcnt,Tcnt;
void add(int a,int b)//原图和逆图都要添加
{
edge1[tol1].to=b;
edge1[tol1].next=head1[a];
head1[a]=tol1++;
edge2[tol2].to=a;
edge2[tol2].next=head2[b];
head2[b]=tol2++;
}
void init()//建图前初始化
{
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(vis1,false,sizeof(vis1));
memset(vis2,false,sizeof(vis2));
tol1=tol2=0;
Bcnt=Tcnt=0;
}
void dfs1(int x)//对原图进行dfs,算出每个结点的结束时间,哪个点开始无所谓
{
vis1[x]=true;
int j;
for(int j=head1[x];j!=-1;j=edge1[j].next)
if(!vis1[edge1[j].to])
dfs1(edge1[j].to);
T[Tcnt++]=x;
}
void dfs2(int x)
{
vis2[x]=true;
Belong[x]=Bcnt;
int j;
for(j=head2[x];j!=-1;j=edge2[j].next)
if(!vis2[edge2[j].to])
dfs2(edge2[j].to);
}
struct Point
{
int x,y;
}s[MAXN];
double dist(Point a,Point b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool ok(int n)//判断可行性
{
for(int i=0;i<2*n;i++)
if(!vis1[i])
dfs1(i);
for(int i=Tcnt-1;i>=0;i--)
if(!vis2[T[i]])//这个别写错,是vis2[T[i]]
{
dfs2(T[i]);
Bcnt++;
}
for(int i=0;i<=2*n-2;i+=2)
if(Belong[i]==Belong[i+1])
return false;
return true;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
double left,right,mid;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d%d%d",&s[2*i].x,&s[2*i].y,&s[2*i+1].x,&s[2*i+1].y);
left=0;
right=40000.0;
while(right-left>=eps)
{
mid=(left+right)/2;
init();
for(int i=0;i<2*n-2;i++)
{
int t;
if(i%2==0)t=i+2;
else t=i+1;
for(int j=t;j<2*n;j++)
if(dist(s[i],s[j])<2*mid)//冲突了
{
add(i,j^1);
add(j,i^1);//注意顺序不能变的
}
}
if(ok(n))left=mid;
else right=mid;
}
printf("%.2lfn",right);
}
return 0;
}
HDU 3622
/*
HDU 3622
G++ 734ms 784K
*/
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=210;
const double eps=1e-5;
char color[MAXN];//染色
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
struct Point
{
int x,y;
}s[MAXN];
double dist(Point a,Point b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
double left,right,mid;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d%d%d",&s[2*i].x,&s[2*i].y,&s[2*i+1].x,&s[2*i+1].y);
left=0;
right=40000.0;
while(right-left>=eps)
{
mid=(left+right)/2;
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
for(int i=0;i<2*n-2;i++)
{
int t;
if(i%2==0)t=i+2;
else t=i+1;
for(int j=t;j<2*n;j++)
if(dist(s[i],s[j])<2*mid)//冲突了
{
//add(i,j^1);
//add(j,i^1);//注意顺序不能变的
adj[i].push_back(j^1);
adj[j].push_back(i^1);
radj[j^1].push_back(i);
radj[i^1].push_back(j);
}
}
korasaju();
if(solvable())left=mid;
else right=mid;
}
printf("%.2lfn",right);
}
return 0;
}
2、HDU 1814 Peaceful Commission
2-sat题目。要求输出字典序最小解。
解题报告见here
输出字典序最小的解的程序:
HDU 1814
/*
HDU 1814
求出字典序最小的解
C++ 2652ms 2316K
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=16010;
const int MAXM=100000;
struct Node
{
int a,b,pre,next;
}E[MAXM],E2[MAXM];
int _n,n,m;
int V[MAXN],ST[MAXN][2],Q[MAXN],Q2[MAXN],vst[MAXN];
bool res_ex;
void init_d()
{
for(int i=0;i<n;i++)
E[i].a=E[i].pre=E[i].next=E2[i].a=E2[i].pre=E2[i].next=i;
m=n;
}
void add_edge(int a,int b)
{
E[m].a=a;E[m].b=b;E[m].pre=E[a].pre;E[m].next=a;E[a].pre=m;E[E[m].pre].next=m;
E2[m].a=b;E2[m].b=a;E2[m].pre=E2[b].pre;E2[m].next=b;E2[b].pre=m;E2[E2[m].pre].next=m;
m++;
}
void solve()
{//1
for(int i=0;i<n;i++)
{
V[i]=0;
vst[i]=0;
}
res_ex=1;
int i,i1,i2,j,k,front,rear,front2,rear2;
int len;
bool ff;
for(int _i=0;_i<_n;_i++)
{//2
if(V[_i<<1]==1||V[(_i<<1)+1]==1)continue;//找一对未确定的点
i=_i<<1;len=0;
if(!V[i])
{//3
ST[len][0]=i;
ST[len++][1]=1;
if(!V[i^1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
ff=1;
for(;front<=rear;front++)
{//4
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{//5
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{//6
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}//6
if(vst[k^1]!=i2)
{//6
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}//6
}//5
if(!ff)break;
}//4
if(ff)
{//4
for(;front2<=rear2;front2++)
{//5
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{//6
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{ff=0;break;}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}//6
if(!ff)break;
}//5
if(ff)
{
for(int j=0;j<len;j++)V[ST[j][0]]=ST[j][1];
continue;
}
}//4
}//3
i=(_i<<1)+1;len=0;
//********************************************
//下面这段和上面完全一样的,可以复制。但是要保证上面写对
//********************************************
if(!V[i])
{//3
ST[len][0]=i;
ST[len++][1]=1;
if(!V[i^1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
ff=1;
for(;front<=rear;front++)
{//4
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{//5
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{//6
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}//6
if(vst[k^1]!=i2)
{//6
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}//6
}//5
if(!ff)break;
}//4
if(ff)
{//4
for(;front2<=rear2;front2++)
{//5
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{//6
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{ff=0;break;}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}//6
if(!ff)break;
}//5
if(ff)
{
for(int j=0;j<len;j++)V[ST[j][0]]=ST[j][1];
continue;
}
}//4
}//3
//**************************************************************
if(V[_i<<1]+V[(_i<<1)+1]!=3){res_ex=0;break;}
}//2
}//1
//点的编号必须从0开始,2*i和2*i+1是一对sat
int main()
{
int M;
int x,y;
while(scanf("%d%d",&_n,&M)!=EOF)
{
n=_n<<1;
init_d();
while(M--)
{
scanf("%d%d",&x,&y);
x--;
y--;
if(x!=(y^1))
{
add_edge(x,y^1);
add_edge(y,x^1);
}
}
solve();
if(res_ex)
{
for(int i=0;i<n;i++)//V为0为不确定,1为确定选择,2为确定不选择
if(V[i]==1)printf("%dn",i+1);
}
else printf("NIEn");
}
return 0;
}
另外写了一个输出任意一组解的程序:
HDU 1814
/*
HDU 1814
任意输出一组可行解。
在HDU上不能AC,HDU 上要求字典序最小的解
*/
//2-SAT问题
//求出所有强连通分量,如果有矛盾点同处于一个连通分量则无解
//缩点,将原图反向建立DAG图//按拓扑排序着色,找一个未着色点x,染成红色
//将与x矛盾的顶点及其子孙染为蓝色
//直到所有顶点均被染色,红色即为2-SAT的一组解
//点的编号从1开始,2*i和2*i+1是一组的
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int MAXN=16010;//8000*2
char color[MAXN];//染色
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,m,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=1;i<=2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=1;i<=n;i++)
if(id[2*i-1]==id[2*i])
return false;
return true;
}
void topsort()
{
int i,j,len,now,p,pid;
while(!q1.empty())
{
now=q1.front();
q1.pop();
if(color[now]!=0)continue;
color[now]='R';
ind[now]=-1;
for(i=1;i<=2*n;i++)
{
if(id[i]==now)
{
p=(i%2)?i+1:i-1;
pid=id[p];
q2.push(pid);
while(!q2.empty())
{
pid=q2.front();
q2.pop();
if(color[pid]=='B')continue;
color[pid]='B';
len=dag[pid].size();
for(j=0;j<len;j++)
q2.push(dag[pid][j]);
}
}
}
len=dag[now].size();
for(i=0;i<len;i++)
{
ind[dag[now][i]]--;
if(ind[dag[now][i]]==0)
q1.push(dag[now][i]);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,j,x,y,xx,yy,len;
while(scanf("%d%d",&n,&m)!=EOF)
{
adj.assign(2*n+1,vector<int>());
radj.assign(2*n+1,vector<int>());
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
xx=(x%2)?x+1:x-1;
yy=(y%2)?y+1:y-1;
adj[x].push_back(yy);
adj[y].push_back(xx);
radj[yy].push_back(x);
radj[xx].push_back(y);
}
korasaju();
if(!solvable())printf("NIEn");
else
{
dag.assign(cnt+1,vector<int>());
memset(ind,0,sizeof(ind));
memset(color,0,sizeof(color));
for(i=1;i<=2*n;i++)
{
len=adj[i].size();
for(j=0;j<len;j++)
if(id[i]!=id[adj[i][j]])
{
dag[id[adj[i][j]]].push_back(id[i]);
ind[id[i]]++;
}
}
for(i=1;i<=cnt;i++)
if(ind[i]==0)
q1.push(i);
topsort();
for(i=1;i<=n;i++)//小心别写错,是color[id[
if(color[id[2*i-1]]=='R')printf("%dn",2*i-1);
else printf("%dn",2*i);
}
}
}
/*
根据宪法,Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。
不幸的是,由于某些党派代表之间的不和睦而使得这件事存在障碍。
此委员会必须满足下列条件:
■每个党派都在委员会中恰有1个代表,
■如果2个代表彼此厌恶,则他们不能都属于委员会。
每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第I个党派。
任务
写一程序:
■从文本文件读入党派的数量和关系不友好的代表对,
■计算决定建立和平委员会是否可能,若行,则列出委员会的成员表,
■结果写入文本文件。
输入
在文本文件的第一个行有2非负整数n和m。 他们各自表示:党派的数量n,1 < =n < =8000和不友好的代表对m,0 <=m <=20000。 在下面m行的每行为一对整数a,b,1<=a <b<=2n,中间用单个空格隔开。 它们表示代表a,b互相厌恶。
输出
如果委员会不能创立,文本文件中应该包括单词NIE。若能够成立,文本文件SPO.OUT中应该包括n个从区间1到2n选出的整数,按升序写出,每行一个,这些数字为委员会中代表的编号。如果委员会能以多种方法形成,程序可以只写他们的某一个。
样品输入
3 2
1 3
2 4样品输出
1
4
5
*/
3、POJ 3207 Ikki's Story IV - Panda's Trick
可行性判断
解题报告见here
POJ 3207
/*
POJ 3207
题意:平面上,一个圆,圆的边上按顺时针放着n个点。现在要连m条边,
比如a,b,那么a到b可以从圆的内部连接,也可以从圆的外部连接。
给你的信息中,每个点最多只会连接的一条边。问能不能连接这m条边,
使这些边都不相交。
思路:对于每条Link,要么在圆外,要么在圆内,且不可同时满足,
只能两者取一,判断这M条Link是否合法,也就是M条Link不冲突,
这就是典型的2-sat问题了。 将每条Link i 看做一个点,如果Link在圆内,
则选做i ,如果在圆外, 则选做i'。对于两条线(i,j) ,如果i,j不能同时
在圆内,也就可以推出两者不能同时在圆外,这个证明很容易,读者可
以自行证明。i, j不能同时在圆内,则有边(i, j') 、(j ,i')、(i',j)、(j' ,i)
(这是由2-sat的构图方式决定的,具体可以看《由对称性解2-SAT问题》
这篇论文)。建图完了之后,本题就是判断2-sat问题是否有解,
先求原图的强连通分量,并缩点,(这里我们称:(i,i')属于同一组),
判断是否存在(i,i')属于同一组,若存在,则不可能,若不存在则可能。
C++ 204MS 2248K
*/
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=1010;
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
struct Node
{
int s,t;
}node[MAXN];
int main()
{
int N;
int x,y;
while(scanf("%d%d",&N,&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
node[i].s=x;
node[i].t=y;
}
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if((node[i].s<node[j].s&&node[j].s<node[i].t&&node[i].t<node[j].t)||(node[j].s<node[i].s&&node[i].s<node[j].t&&node[j].t<node[i].t))
{
adj[2*i].push_back(2*j+1);
adj[2*j+1].push_back(2*i);
adj[2*i+1].push_back(2*j);
adj[2*j].push_back(2*i+1);
radj[2*j+1].push_back(2*i);
radj[2*i].push_back(2*j+1);
radj[2*j].push_back(2*i+1);
radj[2*i+1].push_back(2*j);
}
}
korasaju();
if(solvable())printf("panda is telling the truth...n");
else printf("the evil panda is lying againn");
}
return 0;
}
二分+2-SAT可行性判断
和HDU 3644很相似的方法。
解题报告here
POJ 2296
/*
POJ 2296
二分+2-SAT可行性判断
题意:给你n个点,要你在这n个点上放一个正方形,点
只能在正方形的上边或下边的中点上,所有正方形大小一样,
不能重叠,求最大的正方形。。。
如果abs(s[i].x-s[j].x)>=r则可以随便放
如果 abs[s[i].x-s[j].y)<r;
如果abs(s[i].y-s[j].y)<r,如果s[i].y==s[i].y则要求一个放上面一个放下面。
否则只能是上面的点放上面,下面的点放下面。
如果r<=abs(s[i].y-s[j].y)<2*r,则除了上面的点放下方、下面的点放上方的情况都是可以的。
C++ 422ms 467K
G++ 32ms
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
const int MAXN=220;
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
struct Point
{
int x,y;
}s[MAXN];
int main()
{
int T;
int left,right,mid;
int ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&s[i].x,&s[i].y);
left=0;
right=80000;
while(right-left>=0)
{
mid=(left+right)>>1;
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
//2*i表示放上面的,2*i+1表示放下面
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(abs(s[i].x-s[j].x)>=mid)continue;//没有限制
if(abs(s[i].y-s[j].y)<mid)
{
if(s[i].y==s[j].y)//一个上一个下
{
adj[2*i].push_back(2*j+1);
adj[2*j].push_back(2*i+1);
adj[2*i+1].push_back(2*j);
adj[2*j+1].push_back(2*i);
radj[2*i].push_back(2*j+1);
radj[2*j].push_back(2*i+1);
radj[2*i+1].push_back(2*j);
radj[2*j+1].push_back(2*i);
}
else if(s[i].y>s[j].y)//i放上面,j放下面
{
adj[2*i+1].push_back(2*i);
adj[2*j].push_back(2*j+1);
radj[2*i].push_back(2*i+1);
radj[2*j+1].push_back(2*j);
}
else
{
adj[2*i].push_back(2*i+1);
adj[2*j+1].push_back(2*j);
radj[2*i+1].push_back(2*i);
radj[2*j].push_back(2*j+1);
}
}
else if(abs(s[i].y-s[j].y)<2*mid)//上面的放下面和下面的放上面是不允许的
{
if(s[i].y>s[j].y)
{
adj[2*i+1].push_back(2*j+1);
adj[2*j].push_back(2*i);
radj[2*j+1].push_back(2*i+1);
radj[2*i].push_back(2*j);
}
else
{
adj[2*j+1].push_back(2*i+1);
adj[2*i].push_back(2*j);
radj[2*i+1].push_back(2*j+1);
radj[2*j].push_back(2*i);
}
}
}
korasaju();
if(solvable()){ans=mid;left=mid+1;}
else right=mid-1;
}
printf("%dn",ans);
}
return 0;
}
此题陷进比较多。要输出一组解的2-SAT。
POJ 3648
/*
POJ 3648
【题意】:有一对新人结婚,邀请n对夫妇去参加婚礼。
有一张很长的桌子,人只能坐在桌子的两边,还要满
足下面的要求:1.每对夫妇不能坐在同一侧 2.n对夫妇
之中可能有通奸关系(包括男男,男女,女女),有通
奸关系的不能同时坐在新娘的对面,可以分开坐,可以
同时坐在新娘这一侧。如果存在一种可行的方案,输出
与新娘同侧的人。
输出任意一组解,点的编号从0~2n-1
AC
G++ 16ms 724K
取和新郎同一侧的,输出的时候反一下就变成和新娘同一侧的了
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int MAXN=200;//
char color[MAXN];//染色
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,m,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
void topsort()
{
int i,j,len,now,p,pid;
while(!q1.empty())
{
now=q1.front();
q1.pop();
if(color[now]!=0)continue;
color[now]='R';
ind[now]=-1;
for(i=0;i<2*n;i++)
{
if(id[i]==now)
{
//p=(i%2)?i+1:i-1;//点的编号从0开始以后这一定要修改
p=i^1;
pid=id[p];
q2.push(pid);
while(!q2.empty())
{
pid=q2.front();
q2.pop();
if(color[pid]=='B')continue;
color[pid]='B';
len=dag[pid].size();
for(j=0;j<len;j++)
q2.push(dag[pid][j]);
}
}
}
len=dag[now].size();
for(i=0;i<len;i++)
{
ind[dag[now][i]]--;
if(ind[dag[now][i]]==0)
q1.push(dag[now][i]);
}
}
}
int main()
{
int x,y;
char c1,c2;
int i,j;
int len;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)break;
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
while(m--)
{
scanf("%d%c%d%c",&x,&c1,&y,&c2);
if(c1=='w')x=2*x;
else x=2*x+1;
if(c2=='w')y=2*y;
else y=2*y+1;
if(x!=(y^1))
{
adj[x].push_back(y^1);
adj[y].push_back(x^1);
radj[y^1].push_back(x);
radj[x^1].push_back(y);
}
}
adj[0].push_back(1);
radj[1].push_back(0);
//加一条新娘到新郎的边。
//表示选了新娘必选新郎,这样如果选了新娘就会判断无解。
//这样选出来的组合必定是有新郎的,即和新郎坐在同一侧的
korasaju();
if(!solvable())printf("bad luckn");
else
{
dag.assign(cnt+1,vector<int>());
memset(ind,0,sizeof(ind));
memset(color,0,sizeof(color));
for(i=0;i<2*n;i++)
{
len=adj[i].size();
for(j=0;j<len;j++)
if(id[i]!=id[adj[i][j]])
{
dag[id[adj[i][j]]].push_back(id[i]);
ind[id[i]]++;
}
}
for(i=1;i<=cnt;i++)
if(ind[i]==0)
q1.push(i);
topsort();
for(i=1;i<n;i++)//小心别写错,是color[id[
{
if(i>1)printf(" ");
if(color[id[2*i]]=='R')printf("%dh",i);//选取的是和新郎同一侧的,输出和新娘同一侧的
//所以输出的时候h和w换一下
else printf("%dw",i);
}
printf("n");
}
}
return 0;
}
POJ 3648
/*
POJ3648
【题意】:有一对新人结婚,邀请n对夫妇去参加婚礼。
有一张很长的桌子,人只能坐在桌子的两边,还要满
足下面的要求:1.每对夫妇不能坐在同一侧 2.n对夫妇
之中可能有通奸关系(包括男男,男女,女女),有通
奸关系的不能同时坐在新娘的对面,可以分开坐,可以
同时坐在新娘这一侧。如果存在一种可行的方案,输出
与新娘同侧的人。
求字典序最小的解,点的编号从0~2n-1
G++ 0ms
*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int MAXN=20000;
const int MAXM=100000;//这个必须开大一点
struct Node
{
int a,b,pre,next;
}E[MAXM],E2[MAXM];//原图和逆图
int _n,n,m,V[MAXN],ST[MAXN][2],Q[MAXN],Q2[MAXN],vst[MAXN];
bool res_ex;
void init_d()//初始化
{
for(int i=0;i<n;i++)//相当于建出双重邻接表的头结点
E[i].a=E[i].pre=E[i].next=E2[i].a=E2[i].pre=E2[i].next=i;
m=n;//m是建造双重邻接表时结点的编号
}
void add_edge(int a,int b)//加入边(a,b),需要在原图和逆图中添加边
{//实际上建造出的是循环状的图
E[m].a=a;E[m].b=b;E[m].pre=E[a].pre;E[m].next=a;E[a].pre=m;E[E[m].pre].next=m;
E2[m].a=b;E2[m].b=a;E2[m].pre=E2[b].pre;E2[m].next=b;E2[b].pre=m;E2[E2[m].pre].next=m++;
}
void solve()
{
for(int i=0;i<n;i++)
{
V[i]=0;
vst[i]=0;
}
res_ex=1;
int i,i1,i2,j,k,len,front,rear,front2,rear2;
bool ff;
for(int _i=0;_i<_n;_i++)
{
if(V[_i<<1]==1||V[(_i<<1)+1]==1) continue;//找一对未被确定的点
i=_i<<1;len=0;
if(!V[i])
{
ST[len][0]=i;ST[len++][1]=1;
if(!V[i ^ 1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
//i1,i2为标志量,这样设置标志量使得每次都不一样,省去了初始化
ff=1;
for(;front<=rear;front++)
{
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}
if(vst[k^1]!=i2)
{
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(;front2<=rear2;front2++)
{
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{
ff=0;
break;
}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
continue;
}
}
}
i=(_i<<1)+1;len=0;
if(!V[i])
{
ST[len][0]=i;ST[len++][1]=1;
if(!V[i ^ 1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
ff=1;
for(;front<=rear;front++)
{
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}
if(vst[k^1]!=i2)
{
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(;front2<=rear2;front2++)
{
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{
ff=0;
break;
}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
continue;
}
}
}
if(V[_i<<1]+V[(_i<<1)+1]!=3){res_ex=0;break;}
}
}
int main()
{
int _m,a,b;
char ch1,ch2;
while(scanf("%d%d",&_n,&_m)!=EOF)//_n是点的对数,_m是冲突的点个数
{
if(_n==0&&_m==0)break;
n=_n<<1;
init_d();
for(int i=0;i<_m;i++)
{
scanf("%d%c%d%c",&a,&ch1,&b,&ch2);
if(ch1=='w') a=2*a;
else a=2*a+1;
if(ch2=='w') b=2*b;
else b=2*b+1;
if(a!=(b^1))
{
add_edge(a,b^1);//选a,必选b^1,
add_edge(b,a^1);//选b,必选a^1,
}
}
add_edge(0,1);//加一条新娘到新郎的边。
//表示选了新娘必选新郎,这样如果选了新娘就会判断无解。
//这样选出来的组合必定是有新郎的,即和新郎坐在同一侧的
solve();
bool first=false;
if(res_ex)
{
for(int i=0;i<n;i++)
{
if(V[i]==1&&i!=1)
{
if(first)printf(" ");
else first=true;
printf("%d%c",i/2,i%2==0?'h':'w');//选取的是和新郎同一侧的,输出和新娘同一侧的
//所以输出的时候h和w换一下
}
}
printf("n");
}
else printf("bad luckn");
}
return 0;
}
给出一些两两之间的AND,OR,XOR表达式的值,问有没有解。
经典的2-SAT问题。简单。
POJ 3678
/*
POJ 3678
给出两两之间的AND,OR,XOR的值,判断有没有解
典型的2-SAT
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int MAXN=2200;//
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,m,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
int main()
{
int a,b,c;
char ch[10];
while(scanf("%d%d",&n,&m)!=EOF)
{
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
while(m--)
{
scanf("%d%d%d%s",&a,&b,&c,&ch);
int i=a,j=b;
if(strcmp(ch,"AND")==0)
{
if(c==1)//两个都要取1
{
adj[2*i].push_back(2*i+1);
adj[2*j].push_back(2*j+1);
radj[2*i+1].push_back(2*i);
radj[2*j+1].push_back(2*j);
}
else //不能两个同时取1
{
adj[2*i+1].push_back(2*j);
adj[2*j+1].push_back(2*i);
radj[2*j].push_back(2*i+1);
radj[2*i].push_back(2*j+1);
}
}
else if(strcmp(ch,"OR")==0)
{
if(c==0)//两个都要为0
{
adj[2*i+1].push_back(2*i);
adj[2*j+1].push_back(2*j);
radj[2*i].push_back(2*i+1);
radj[2*j].push_back(2*j+1);
}
else
{
adj[2*i].push_back(2*j+1);
adj[2*j].push_back(2*i+1);
radj[2*j+1].push_back(2*i);
radj[2*i+1].push_back(2*j);
}
}
else
{
if(c==0)//要相同
{
adj[2*i].push_back(2*j);
adj[2*j].push_back(2*i);
adj[2*i+1].push_back(2*j+1);
adj[2*j+1].push_back(2*i+1);
radj[2*i].push_back(2*j);
radj[2*j].push_back(2*i);
radj[2*i+1].push_back(2*j+1);
radj[2*j+1].push_back(2*i+1);
}
else
{
adj[2*i].push_back(2*j+1);
adj[2*j].push_back(2*i+1);
adj[2*i+1].push_back(2*j);
adj[2*j+1].push_back(2*i);
radj[2*i].push_back(2*j+1);
radj[2*j].push_back(2*i+1);
radj[2*i+1].push_back(2*j);
radj[2*j+1].push_back(2*i);
}
}
}
korasaju();
if(solvable())printf("YESn");
else printf("NOn");
}
return 0;
}
7、HDU 4115 Eliminate the Conflict
2-SAT判断是否有解问题。主要是要细心,注意细节。
HDU 4115
/*
HDU 4115
题意:
有两个人玩一个石头剪刀布的游戏,两个人连续玩N轮,给出其中
一个人的N轮出的情况和该人对另外一个人的一些限制条件,有两种限制:
每种限制表示为:(a,b,c) ,如果c==0 则表示该人对另外一个人的限制为第a
局和第b局出的应该一样,如果c==1表示不一样,问另外一个人是否有赢的
可能。
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int MAXN=22000;//
bool visit[MAXN];
queue<int>q1,q2;
//vector建图方法很妙
vector<vector<int> >adj; //原图 //中间一定要加空格把两个'>'隔开
vector<vector<int> >radj;//逆图
vector<vector<int> >dag;//缩点后的逆向DAG图
int n,m,cnt;
int id[MAXN],order[MAXN],ind[MAXN];//强连通分量,访问顺序,入度
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u)
{
visit[u]=true;
id[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju()
{
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=0;i<2*n;i++)
if(!visit[i])
dfs(i);
memset(id,0,sizeof(id));
memset(visit,false,sizeof(visit));
for(cnt=0,i=2*n-1;i>=0;i--)
if(!visit[order[i]])
{
cnt++;//这个一定要放前面来
rdfs(order[i]);
}
}
bool solvable()
{
for(int i=0;i<n;i++)
if(id[2*i]==id[2*i+1])
return false;
return true;
}
void add(int x,int y)
{
adj[x].push_back(y);
radj[y].push_back(x);
}
int a[MAXN],b[MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int x,y,z;
scanf("%d",&T);
int iCase=0;
while(T--)
{
iCase++;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]==1)b[i]=2;
else if(a[i]==2)b[i]=3;
else b[i]=1;
if(a[i]>b[i])swap(a[i],b[i]);
}
adj.assign(2*n,vector<int>());
radj.assign(2*n,vector<int>());
bool flag=true;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
x--;
y--;
if(!flag)continue;
if(x==y)
{
if(z==1)flag=false;
continue;
}
if(z==0)//要相等
{
/* //这种加边方法也可以
if(a[x]==a[y]&&b[x]==b[y])
{
adj[2*x].push_back(2*y);
adj[2*y].push_back(2*x);
adj[2*x+1].push_back(2*y+1);
adj[2*y+1].push_back(2*x+1);
radj[2*x].push_back(2*y);
radj[2*y].push_back(2*x);
radj[2*x+1].push_back(2*y+1);
radj[2*y+1].push_back(2*x+1);
}
else if(a[x]==a[y]&&b[x]!=b[y])//只能选a
{
adj[2*x+1].push_back(2*x);
adj[2*y+1].push_back(2*y);
radj[2*x].push_back(2*x+1);
radj[2*y].push_back(2*y+1);
}
else if(a[x]!=a[y]&&b[x]==b[y])//只能选b
{
adj[2*x].push_back(2*x+1);
adj[2*y].push_back(2*y+1);
radj[2*x+1].push_back(2*x);
radj[2*y+1].push_back(2*y);
}
else if(a[x]==b[y])//23和12
{
adj[2*x+1].push_back(2*x);
adj[2*y].push_back(2*y+1);
radj[2*x].push_back(2*x+1);
radj[2*y+1].push_back(2*y);
}
else if(b[x]==a[y])
{
adj[2*x].push_back(2*x+1);
adj[2*y+1].push_back(2*y);
radj[2*x+1].push_back(2*x);
radj[2*y].push_back(2*y+1);
}
*/
if(a[x]!=a[y])
{
add(2*x,2*y+1);
add(2*y,2*x+1);
}
if(a[x]!=b[y])
{
add(2*x,2*y);
add(2*y+1,2*x+1);
}
if(b[x]!=a[y])
{
add(2*x+1,2*y+1);
add(2*y,2*x);
}
if(b[x]!=b[y])
{
add(2*x+1,2*y);
add(2*y+1,2*x);
}
}
else if(z==1)
{
/* //这种加边方法也可以
if(a[x]==a[y]&&b[x]==b[y])
{
adj[2*x].push_back(2*y+1);
adj[2*y].push_back(2*x+1);
adj[2*x+1].push_back(2*y);
adj[2*y+1].push_back(2*x);
radj[2*x+1].push_back(2*y);
radj[2*y+1].push_back(2*x);
radj[2*x].push_back(2*y+1);
radj[2*y].push_back(2*x+1);
}
else if(a[x]==a[y]&&b[x]!=b[y])
{
adj[2*x].push_back(2*y+1);
adj[2*y].push_back(2*x+1);
radj[2*y+1].push_back(2*x);
radj[2*x+1].push_back(2*y);
}
else if(a[x]!=a[y]&&b[x]==b[y])
{
adj[2*x+1].push_back(2*y);
adj[2*y+1].push_back(2*x);
radj[2*y].push_back(2*x+1);
radj[2*x].push_back(2*y+1);
}
else if(a[x]==b[y])
{
adj[2*x].push_back(2*y);
adj[2*y+1].push_back(2*x+1);
radj[2*y].push_back(2*x);
radj[2*x+1].push_back(2*y+1);
}
else if(b[x]==a[y])
{
adj[2*x+1].push_back(2*y+1);
adj[2*y].push_back(2*x);
radj[2*y+1].push_back(2*x+1);
radj[2*x].push_back(2*y);
}
*/
if(a[x]==a[y])
{
add(2*x,2*y+1);
add(2*y,2*x+1);
}
if(a[x]==b[y])
{
add(2*x,2*y);
add(2*y+1,2*x+1);
}
if(b[x]==a[y])
{
add(2*x+1,2*y+1);
add(2*y,2*x);
}
if(b[x]==b[y])
{
add(2*x+1,2*y);
add(2*y+1,2*x);
}
}
}
if(!flag)
{
printf("Case #%d: non",iCase);
continue;
}
korasaju();
if(solvable())printf("Case #%d: yesn",iCase);
else printf("Case #%d: non",iCase);
}
return 0;
}
今年2-SAT就做到此吧!希望此次长春RP爆发~~~~2012-10-7
原文链接: https://www.cnblogs.com/kuangbin/archive/2012/10/05/2712429.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/64940
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!