admin管理员组文章数量:1596344
Eliminate the Conflict
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1118 Accepted Submission(s): 472
Problem Description Conflicts are everywhere in the world, from the young to the elderly, from families to countries. Conflicts cause quarrels, fights or even wars. How wonderful the world will be if all conflicts can be eliminated.
Edward contributes his lifetime to invent a 'Conflict Resolution Terminal' and he has finally succeeded. This magic item has the ability to eliminate all the conflicts. It works like this:
If any two people have conflict, they should simply put their hands into the 'Conflict Resolution Terminal' (which is simply a plastic tube). Then they play 'Rock, Paper and Scissors' in it. After they have decided what they will play, the tube should be opened and no one will have the chance to change. Finally, the winner have the right to rule and the loser should obey it. Conflict Eliminated!
But the game is not that fair, because people may be following some patterns when they play, and if the pattern is founded by others, the others will win definitely.
Alice and Bob always have conflicts with each other so they use the 'Conflict Resolution Terminal' a lot. Sadly for Bob, Alice found his pattern and can predict how Bob plays precisely. She is very kind that doesn't want to take advantage of that. So she tells Bob about it and they come up with a new way of eliminate the conflict:
They will play the 'Rock, Paper and Scissors' for N round. Bob will set up some restricts on Alice.
But the restrict can only be in the form of "you must play the same (or different) on the ith and jth rounds". If Alice loses in any round or break any of the rules she loses, otherwise she wins.
Will Alice have a chance to win?
Input The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains two integers N,M(1 <= N <= 10000, 1 <= M <= 10000), representing how many round they will play and how many restricts are there for Alice.
The next line contains N integers B 1,B 2, ...,B N, where B i represents what item Bob will play in the i th round. 1 represents Rock, 2 represents Paper, 3 represents Scissors.
The following M lines each contains three integers A,B,K(1 <= A,B <= N,K = 0 or 1) represent a restrict for Alice. If K equals 0, Alice must play the same on A th and B th round. If K equals 1, she must play different items on Ath and Bthround.
Output For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is "yes" or "no" represents whether Alice has a chance to win.
Sample Input
2 3 3 1 1 1 1 2 1 1 3 1 2 3 1 5 5 1 2 3 2 1 1 2 1 1 3 1 1 4 1 1 5 1 2 3 0
Sample Output
Case #1: no
Case #2: yes
Hint
'Rock, Paper and Scissors' is a game which played by two person. They should play Rock, Paper or Scissors by their hands at the same time.
Rock defeats scissors, scissors defeats paper and paper defeats rock. If two people play the same item, the game is tied..
题意：Bob和Alice玩剪刀石头布的游戏，游戏有n个回合。Alice事先已经知道Bob分别在这n个回合里会出什么。游戏有m个约束条件A B K，若K=0，则Alice在回合A和回合B出的必须是相同的，若K=1，则Alice在回合A和回合B出的必须是不相同的。规定若Alice违反任何一个约束条件或者Alice在任何一个回合输了，则Alice在整个游戏输了。给出上述情况，问Alice是否有机会赢。
思路：要使Alice有机会赢，则要保证Alice不违反任何一个约束条件，而且任何一个回合，要么Alice赢，要么平手，这样对于每一个回合，Alice都有两个选择，符合2-sat问题。可以先根据Bob每个回合出什么，记录Alice在每个回合的两种选择。然后还要根据约束条件找矛盾的关系，构图。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <cstdlib>
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
#define ll long long
#define eps 1e-6
using namespace std;
const int maxn=20005;
struct node
{
int v,next;
}edge[maxn*20];
int head[maxn],scc[maxn],stack[maxn];
int low[maxn],dfn[maxn],alice[maxn];
bool ins[maxn];
int n,m,num,cnt,top,snum;
void init()
{
memset(head,-1,sizeof(head));
num=0;
}
void add(int u,int v)
{
edge[num].v=v;
edge[num].next=head[u];
head[u]=num++;
}
void input()
{
int bob,a,b,k;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&bob);
if(bob==1||bob==2)
{
alice[i]=bob;
alice[i+n]=bob+1;
}
else
{
alice[i]=3;
alice[i+n]=1;
}
}
while(m--)
{
scanf("%d%d%d",&a,&b,&k);
if(k==0)
{
if(alice[a]!=alice[b])
{
add(a,b+n);
add(b,a+n);
}
if(alice[a]!=alice[b+n])
{
add(a,b);
add(b+n,a+n);
}
if(alice[a+n]!=alice[b])
{
add(a+n,b+n);
add(b,a);
}
if(alice[a+n]!=alice[b+n])
{
add(a+n,b);
add(b+n,a);
}
}
else
{
if(alice[a]==alice[b])
{
add(a,b+n);
add(b,a+n);
}
if(alice[a]==alice[b+n])
{
add(a,b);
add(b+n,a+n);
}
if(alice[a+n]==alice[b])
{
add(a+n,b+n);
add(b,a);
}
if(alice[a+n]==alice[b+n])
{
add(a+n,b);
add(b+n,a);
}
}
}
}
void dfs(int u)
{
int x;
dfn[u]=low[u]=++cnt;
stack[top++]=u;
ins[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
snum++;
do{
x=stack[--top];
ins[x]=false;
scc[x]=snum;
}while(x!=u);
}
}
void tarjan()
{
memset(dfn,0,sizeof(dfn));
memset(ins,false,sizeof(ins));
cnt=top=snum=0;
for(int i=1;i<=2*n;i++)
if(!dfn[i]) dfs(i);
}
void solve()
{
for(int i=1;i<=n;i++)
if(scc[i]==scc[i+n])
{
printf("no\n");
return;
}
printf("yes\n");
}
int main()
{
int t,c=0;
scanf("%d",&t);
while(t--)
{
init();
input();
tarjan();
printf("Case #%d: ",++c);
solve();
}
return 0;
}
版权声明：本文标题：hdu 4115 Eliminate the Conflict 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1728255890a1151008.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论