首页 > ACM题库 > HDU-杭电 > HDU 4115-Eliminate the Conflict-图-[解题报告]HOJ
2015
04-16

HDU 4115-Eliminate the Conflict-图-[解题报告]HOJ

Eliminate the Conflict

问题描述 :

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?

输入:

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 B1,B2, …,BN, where Bi represents what item Bob will play in the ith 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 Ath and Bth round. If K equals 1, she must play different items on Ath and Bthround.

输出:

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 B1,B2, …,BN, where Bi represents what item Bob will play in the ith 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 Ath and Bth round. If K equals 1, she must play different items on Ath and Bthround.

样例输入:

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

样例输出:

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..

【题目链接】

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

同理,第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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shuangde800/article/details/8875505


,
  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。