admin管理员组文章数量:1596415
HDU 4115 Eliminate the Conflict (2-SAT)
http://acm.hdu.edu/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的所有出拳,所以用a[maxn][2]数组保存那些出拳的结果。然后对于下面的要求作出Alice在第i轮选0还是选1的推断即可。看看是否有方法满足本2-SAT的n个解。
因为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;
}
版权声明:本文标题:HDU 4115 Eliminate the Conflict (2-SAT) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728255739a1150990.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论