首页 > 搜索 > DFS搜索 > HDU 3094-A tree game-DFS-[解题报告]HOJ
2014
03-02

HDU 3094-A tree game-DFS-[解题报告]HOJ

A tree game

问题描述 :

Alice and Bob want to play an interesting game on a tree.
Given is a tree on N vertices, The vertices are numbered from 1 to N. vertex 1 represents the root. There are N-1 edges. Players alternate in making moves, Alice moves first. A move consists of two steps. In the first step the player selects an edge and removes it from the tree. In the second step he/she removes all the edges that are no longer connected to the root. The player who has no edge to remove loses.
You may assume that both Alice and Bob play optimally.

输入:

The first line of the input file contains an integer T (T<=100) specifying the number of test cases.
Each test case begins with a line containing an integer N (1<=N<=10^5), the number of vertices,The following N-1 lines each contain two integers I , J, which means I is connected with J. You can assume that there are no loops in the tree.

输出:

The first line of the input file contains an integer T (T<=100) specifying the number of test cases.
Each test case begins with a line containing an integer N (1<=N<=10^5), the number of vertices,The following N-1 lines each contain two integers I , J, which means I is connected with J. You can assume that there are no loops in the tree.

样例输入:

3
3
1 2
2 3

3
1 2
1 3 

10
6 2
4 3
8 4
9 5
8 6
2 7
5 8
1 9
6 10

样例输出:

Alice
Bob
Alice

经典的树形游戏的博弈

题目给定一棵树,虽然是规定给定一棵根为1树,但数据给的是树枝,所以是无向的,坑爹啊

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
const int N = 100000+10;
vector<int> g[N];
bool vis[N];
int w[N];
void dfs(int u)
{
    vis[u]=true;
    int size=g[u].size();
    w[u]=0;
    for(int i=0;i<size;i++)
    {
        int v=g[u][i];
        if(vis[v]) continue;
        dfs(v);
        w[u]^=(w[v]+1);
    }
}
int main()
{
    int T,n;
    int a,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
            g[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d %d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        memset(vis,false,sizeof(vis));
        dfs(1);
        if(w[1])
            puts("Alice");
        else puts("Bob");
    }
    return 0;
}

 

参考:http://www.cnblogs.com/nanke/archive/2012/04/20/2459210.html


,
  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  4. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测