admin管理员组文章数量:1596328
【题目链接】
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出的拳,Alice只可以赢或者平局,即每次有两种选择,是2-SAT模型
然后会有一些矛盾对,假设第a次可以出a1,a2, 第b次可以出b1和b2
如果第a次和b次要求相同, 但是a1和b1不同,说明这个矛盾,建立连接 a1—>b2, b1—>a2
同理,第a次和b次要求不相同,但是a1和b2相同,说明这个矛盾,建立链接a1—>b1, b2—>a2
……
然后用2-SAT判断即可
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int64;
const int MAXN = 10010;
const int VN = MAXN*2;
const int EN = VN*3;
int n, m;
int pat[MAXN];
int alice[MAXN][2];
struct Edge{
int v, next;
};
class Graph{
public:
void init(){
size = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v){
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
public:
int head[VN];
Edge E[EN];
private:
int size;
}g;
class Two_Sat{
public:
bool check(const Graph&g, const int n){
scc(g, n);
for(int i=0; i<n; ++i)
if(belong[2*i] == belong[2*i+1])
return false;
return true;
}
private:
void tarjan(const Graph&g, const int u){
int v;
DFN[u] = low[u] = ++idx;
sta[top++] = u;
inStack[u] = true;
for(int e=g.head[u]; e!=-1; e=g.E[e].next){
v = g.E[e].v;
if(DFN[v] == -1){
tarjan(g, v);
low[u] = min(low[u], low[v]);
}else if(inStack[v]){
low[u] = min(low[u], DFN[v]);
}
}
if(DFN[u] == low[u]){
++bcnt;
do{
v = sta[--top];
inStack[v] = false;
belong[v] = bcnt;
}while(u != v);
}
}
void scc(const Graph& g, int n){
top = idx = bcnt = 0;
memset(DFN, -1, sizeof(DFN));
memset(inStack, 0, sizeof(inStack));
for(int i=0; i<2*n; ++i)
if(DFN[i] == -1)
tarjan(g, i);
}
private:
int top, idx, bcnt;
int sta[VN];
int DFN[VN];
int low[VN];
int belong[VN];
bool inStack[VN];
}sat;
int main(){
int nCase;
int cas=1;
int a, b, c;
scanf("%d", &nCase);
while(nCase--){
g.init();
scanf("%d%d", &n,&m);
for(int i=0; i<n; ++i){
scanf("%d", &pat[i]);
pat[i]--;
alice[i][0] = pat[i];
alice[i][1] = (pat[i]+1)%3;
}
for(int i=0; i<m; ++i){
scanf("%d%d%d", &a,&b,&c);
--a, --b;
if(c){ // a,b不同
if(alice[a][0]==alice[b][0])
g.addEdge(a*2, b*2+1), g.addEdge(b*2, a*2+1);
if(alice[a][0]==alice[b][1])
g.addEdge(a*2, b*2), g.addEdge(b*2+1, a*2+1);
if(alice[a][1]==alice[b][0])
g.addEdge(a*2+1, b*2+1), g.addEdge(b*2, a*2);
if(alice[a][1]==alice[b][1])
g.addEdge(a*2+1, b*2), g.addEdge(b*2+1, a*2);
}else{ // a, b相同
if(alice[a][0]!=alice[b][0])
g.addEdge(a*2, b*2+1), g.addEdge(b*2, a*2+1);
if(alice[a][0]!=alice[b][1])
g.addEdge(a*2, b*2), g.addEdge(b*2+1, a*2+1);
if(alice[a][1]!=alice[b][0])
g.addEdge(a*2+1, b*2+1), g.addEdge(b*2, a*2);
if(alice[a][1]!=alice[b][1])
g.addEdge(a*2+1, b*2), g.addEdge(b*2+1, a*2);
}
}
printf("Case #%d: ", cas++);
if(sat.check(g, n)) puts("yes");
else puts("no");
}
return 0;
}
版权声明:本文标题:HDU 4115Eliminate the Conflict (2-SAT判断) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728255840a1151002.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论