首页 > ACM题库 > HDU-杭电 > HDU 3267-Graph Game[解题报告]HOJ
2014
03-13

HDU 3267-Graph Game[解题报告]HOJ

Graph Game

问题描述 :

Consider the following game on an undirected graph G. There are two players, a red color player R and a blue color player B. Initially all edges of G are uncolored. The two players alternately color an uncolored edge of G with their color until all edges are colored. The goal of B is that in the end, the blue-colored edges form a connected spanning subgraph of G. A connected spanning subgraph of G is a connected subgraph that contains all the vertexes of graph G. The goal of R is to prevent B from achieving his goal.

Assume that R starts the game. Suppose that both players play in the smartest way. Your task is to find out whether B will win the game.

输入:

The input contains several test cases, ended by a line of “-1 -1”.
Each test case begins with a line of two integers n ( 1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n-1.
Then m lines follow. Each line contains two integers p and q ( 0 <= p, q < n) , indicating there is an edge between vertex p and vertex q.
It is possible that the graph contains more than one edge between two vertexes and self-loops.

输出:

The input contains several test cases, ended by a line of “-1 -1”.
Each test case begins with a line of two integers n ( 1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n-1.
Then m lines follow. Each line contains two integers p and q ( 0 <= p, q < n) , indicating there is an edge between vertex p and vertex q.
It is possible that the graph contains more than one edge between two vertexes and self-loops.

样例输入:

3 4
0 1
1 2
2 0
0 2
4 6
1 0
1 2
2 0
0 2
3 0
1 0
-1 -1

样例输出:

YES
NO

#include <stdio.h>
#include <string.h>

#define MAXN 20
#define MAXM 2000

struct Edge{
 int u, v;
}edge[MAXM];

int n, m, cnt, fa[MAXN], d1[MAXM], d2[MAXM];
bool used[MAXN];
bool solved;

int findset(int u){
 int v = fa[u];
 while(u != fa[u]) u = fa[u];
 while(fa[v] != u){
 int t = fa[v];
 fa[v] = u;
 t = v;
 }
 return u;
}

bool check1(){
 for(int i = 0; i < n; ++i) fa[i] = i;
 for(int i = 0; i < cnt; ++i){
 int x = findset(d1[i]), y = findset(d2[i]);
 if(x == y) return false;
 fa[y] = x;
 }
 return true;
}

bool check2(){
 for(int i = 0; i < n; ++i) fa[i] = i;
 int total = 1;
 for(int i = 0; i < m && total < n; ++i){
 if(used[i]) continue;
 int x = findset(edge[i].u), y = findset(edge[i].v);
 if(x != y){
 fa[y] = x;
 ++total;
 }
 }
 return total == n;
}

void dfs(int level){
 if(cnt == n - 1){
 if(check2()) solved = true;
 return;
 }
 if(m - level - 1 + cnt >= n - 1 && !solved) dfs(level + 1);
 d1[cnt] = edge[level].u, d2[cnt++] = edge[level].v;
 used[level] = true;
 if(!solved && check1())
 dfs(level + 1);
 used[level] = false;
 --cnt;
}

int main(){
 while(scanf("%d%d", &n, &m), n != -1){
 cnt = 0;
 solved = false;
 memset(used, false, sizeof(used));
 for(int i = 0; i < m; ++i) scanf("%d%d", &edge[i].u, &edge[i].v);
 dfs(0);
 if(solved) puts("YES");
 else puts("NO");
 }
 return 0;
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience