HDU 4115 Eliminate the Conflict (2-SAT)
http://acm.hdu.edu.cn/showproblem.php?pid=4115
题意: Bob和Alice玩剪刀石头布,一个玩n轮,Alice已经知道了Bob每次要出什么,1代表剪刀,2代表石头,3代表布,然后Bob对Alice作出了一些限制:
给m行,每行是a b k,如果k是0,表示Alice第a次和b次出的拳必须相同,如果k是1,表示Alice第a次和b次出的拳必须不相同。
一但Alice破坏了这个限制规则,或者输了一局,那么Alice就彻底输了。
问Alice可不可能赢?
分析:
因为Alice一次都不能输,所以根据Bob出的拳,Alice只可以赢或者平局,即每次有两种选择,是2-SAT模型
然后会有一些矛盾对,假设第a次可以出a1,a2, 第b次可以出b1和b2
如果第a次和b次要求相同, 但是a1和b1不同,说明这个矛盾,建立连接 a1—>b2, b1—>a2.(a1与b1不同时最多有4种可能的情况需要考虑)
同理,第a次和b次要求不相同,但是a1和b2相同,说明这个矛盾,建立链接a1—>b1, b2—>a2
……
然后用2-SAT判断即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10000+10;
int n,m;
int a[maxn][2];
struct TwoSAT
{
int n;
vector<int> G[maxn*2];
int S[maxn*2],c;
bool mark[maxn*2];
bool dfs(int x)
{
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x]=true;
S[c++]=x;
for(int i=0;i<G[x].size();i++)
if(!dfs(G[x][i])) return false;
return true;
}
void init(int n)
{
this->n=n;
for(int i=0;i<2*n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}
void add_clause(int x,int xval,int y,int yval)
{
x=x*2+xval;
y=y*2+yval;
G[x].push_back(y);
}
bool solve()
{
for(int i=0;i<2*n;i+=2)
if(!mark[i] && !mark[i+1])
{
c=0;
if(!dfs(i))
{
while(c>0) mark[S[--c]]=false;
if(!dfs(i+1)) return false;
}
}
return true;
}
}TS;
int main()
{
int T;
scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d%d",&n,&m);
TS.init(n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i][0]);
a[i][0]--;
a[i][1] = (a[i][0]+1)%3;
}
for(int i=0;i<m;i++)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
u--,v--;
if(val==0) //第u轮与第v轮必须相等
{
if(a[u][0] != a[v][0])
{
TS.add_clause(u,0,v,1);
TS.add_clause(v,0,u,1);
}
if(a[u][0] != a[v][1])
{
TS.add_clause(u,0,v,0);
TS.add_clause(v,1,u,1);
}
if(a[u][1] != a[v][0])
{
TS.add_clause(u,1,v,1);
TS.add_clause(v,0,u,0);
}
if(a[u][1] != a[v][1])
{
TS.add_clause(u,1,v,0);
TS.add_clause(v,1,u,0);
}
}
else if(val==1) //不等
{
if(a[u][0] == a[v][0])
{
TS.add_clause(u,0,v,1);
TS.add_clause(v,0,u,1);
}
if(a[u][0] == a[v][1])
{
TS.add_clause(u,0,v,0);
TS.add_clause(v,1,u,1);
}
if(a[u][1] == a[v][0])
{
TS.add_clause(u,1,v,1);
TS.add_clause(v,0,u,0);
}
if(a[u][1] == a[v][1])
{
TS.add_clause(u,1,v,0);
TS.add_clause(v,1,u,0);
}
}
}
printf("Case #%d: %s\n",kase,TS.solve()?"yes":"no");
}
return 0;
}
分享到:
相关推荐
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
题目连接 题意: 求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: ... Tarjan求有向图的强连通分量, ...
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器