首页 > ACM题库 > HDU-杭电 > HDU 3904-Hurry Up-图-[解题报告]HOJ
2015
04-14

HDU 3904-Hurry Up-图-[解题报告]HOJ

Hurry Up

问题描述 :

Now I’m in my school and I want to go back home as on time. However my bicycle has been stolen, which means I have to take buses. Let’s consider the bus-net as a diagram. Vertices of the diagram (numbered 1, 2,…, N), correspond to stations, edges <pi, pj>(pi != pj), denote that there is a direct connections from the station pi to the station pj (1<= pi, pj <= N). Transportation lines are numbered 1, 2,…, K. The L-th transportation line is defined as a series of stations pL,1, pL,2,…, pL,sL, on which vehicles of the L-th line stop, and durations rL,1, rL,2,…,rL,sL-1 of traveling between stations— rL,1 is the time necessary to get from the station pL,1 to the station pL,2, or vice versa (i.e. from the station pL,2 to the station pL,1); rL,2 is the time necessary to get from the station pL,2 to pL,3, etc. All the stations of a line are different (i.e. i != j, implies pL,i != pL,j). In the L-th transportation line, buses run with certain frequency cL, and cL is a number from the set {6, 10, 12, 15, 20, 30, and 60}. The buses in the L-th transportation line, start from the station pL,1 at each hour of the day and night, g:0, (0<= g <=23), and then according to the frequency of the line i.e. at g:cL, g:2cL,… etc. (g:cL means cL minutes after hour g). Buses of the L-th line run in two directions: from the station pL,1 to pL,sL, and from the station pL,sL to pL,1. The hours of departure of the buses of the L-th transportation line from the station pL,sL are the same as from the station pL,1. In such a bus-net, we want to have a trip from the start station X which is near my school to the finish station Y which is near my home. During the trip one can change transportation lines, if he/she wants to. Say, the time of a change is equal to 0, however, while changing the line we have to take under consideration the time of waiting for the bus that we want to get into. Because of my poor memory, I can only change the line in no more than T (1<= T <= 20) times. And your task is to find a way from the start station X, to the finish station Y in W (0<= W <= 1440) minutes and change the lines as few as possible, if there are many ways to go back home and change the same least times of bus, choose the quickest one.

输入:

In the first line there are written 8 integers, separated by single spaces:
N (1<= N <=200, number of stations), K (1<= K <=300, number of lines), X (1<= X <=N, the start station), Y (1<= Y <=N, X != Y, the finish station), GX (0<= GX <=23, the hour of the beginning of the trip), MX (0 <= MX <= 59, the minute of the beginning of the trip), W (0<= W <= 1440, the minute you must go back home within), T (1<= T <= 20, the times of changing line).

The stations are numbered from 1 to N, the transportation lines from 1 to K. In the following 3K lines the transportation lines are described – the description of each of them takes three consecutive lines.

In the first line describing the L-th transportation line, there are written two integers, separated by a single space: sL, the number of stations (2<= sL <=N), and cL – the frequency with which the vehicles run (cL belongs to: {6, 10, 12, 15, 20, 30, 60}).

In the second line describing the L-th transportation line, there are sL different integers, separated by single spaces: pL,1,pL,2,…,pL,sL — the numbers of consecutive stations on the transportation line NO. L (1<= pL,i <=N, for 1<= i <=sL).In the third line describing the L-th transportation line, there are written sL-1 integers separated by single spaces: rL,1, rL,2,…, rL,sL-1 — the times (in minutes) necessary to go between the consecutive stations of this transportation line (1<= rL,i <=240, for 1<= i <=sL-1).
The total number of stations on all transportation lines is not greater than 4000 (i.e. s1+s2+…+sK <= 4000).

输出:

In the first line there are written 8 integers, separated by single spaces:
N (1<= N <=200, number of stations), K (1<= K <=300, number of lines), X (1<= X <=N, the start station), Y (1<= Y <=N, X != Y, the finish station), GX (0<= GX <=23, the hour of the beginning of the trip), MX (0 <= MX <= 59, the minute of the beginning of the trip), W (0<= W <= 1440, the minute you must go back home within), T (1<= T <= 20, the times of changing line).

The stations are numbered from 1 to N, the transportation lines from 1 to K. In the following 3K lines the transportation lines are described – the description of each of them takes three consecutive lines.

In the first line describing the L-th transportation line, there are written two integers, separated by a single space: sL, the number of stations (2<= sL <=N), and cL – the frequency with which the vehicles run (cL belongs to: {6, 10, 12, 15, 20, 30, 60}).

In the second line describing the L-th transportation line, there are sL different integers, separated by single spaces: pL,1,pL,2,…,pL,sL — the numbers of consecutive stations on the transportation line NO. L (1<= pL,i <=N, for 1<= i <=sL).In the third line describing the L-th transportation line, there are written sL-1 integers separated by single spaces: rL,1, rL,2,…, rL,sL-1 — the times (in minutes) necessary to go between the consecutive stations of this transportation line (1<= rL,i <=240, for 1<= i <=sL-1).
The total number of stations on all transportation lines is not greater than 4000 (i.e. s1+s2+…+sK <= 4000).

样例输入:

6 2 5 6 23 30 1440 20
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11

样例输出:

1 0 16

题目:题目链接

题意:有一棵树,每一次操作有两步,第一步选择一条边删除,第二步把没有和根相连的边和点全部移走。最后操作的获胜。

叶子节点的SG值为0;中间节点的SG值为它的所有子节点的SG值加1 后的异或和。

在操作的时候,由于是树,当作无向来做,加入两条边,然后递归的时候带入父节点,避免重复。 


代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
vector<int>v[100005];
int get_sg(int u,int pre){
    int ret=0;
    for(int i=0;i<v[u].size();i++){
        if(v[u][i]!=pre)
            ret^=(1+get_sg(v[u][i],u));
    }
    return ret;
}
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        if(get_sg(1,-1))
            puts("Alice");
        else
            puts("Bob");
    }
    return 0;
}

努力努力…

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

参考:http://blog.csdn.net/acm_zl/article/details/9409451


,