快来救救孩子吧
  • 板块灌水区
  • 楼主Zq_water
  • 当前回复1
  • 已保存回复3
  • 发布时间2023/11/11 11:50
  • 上次更新2023/11/11 14:33:40
查看原帖
快来救救孩子吧
895435
Zq_water楼主2023/11/11 11:50

求救,2-SAT最后为什么要选择编号较小的啊,蒟蒻想了好久都没想明白。

signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1,a,x,b,y;i<=m;i++){
		scanf("%d %d %d %d",&a,&x,&b,&y);
		if(x==0&&y==0) add(a+n,b),add(b+n,a);
		if(x==0&&y==1) add(a+n,b+n),add(b,a);
		if(x==1&&y==0) add(a,b),add(b+n,a+n);
		if(x==1&&y==1) add(a,b+n),add(b,a+n);
	}
	for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++){
		if(col[i]==col[i+n]){
			printf("IMPOSSIBLE\n");
			return 0; 
		}
	}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++){
		if(col[i]>col[i+n]) printf("1 ");//这个地方,为什么要优先原则编号小的节点啊
		else printf("0 ");
	} 
	return 0;
}
2023/11/11 11:50
加载中...