首页 > ACM题库 > HDU-杭电 > hdu 1980 Game!just a game!待解决[解题报告]C++
2013
12-26

hdu 1980 Game!just a game!待解决[解题报告]C++

Game!just a game!

问题描述 :

This game is played by two persons, who are regarded as the Positive player (P player) and the Negative player (N player). There is a graph G=(V, E ) with P vertexs and Q bidirectional edges between the vertexs. Sometimes there are a lot of edges between two vertexs, and all the edges differ from each other. V1 is the first vertex and Vp is the last vertex.

  Everytime P player marks a ‘+’ on one of the remained edges which have neither a ‘+’ nor ‘-‘ at all, and N player marks a ‘-‘ on that kind of edges without any marks. At the beginning, N player acts first, and then P player does, and then N player does alternately. The game comes to an end when all the edges are marked with either a ‘+’ or a ‘-‘.
  Now we give the rules to judge the winner:
1)  If there exists a road from V1 to Vp, whose edges are all marked with ‘+’, P player wins the game ultimately. So we can see, P player tries his best to create a such road to win the game.
2)  If there exists none such road ,whose edges are all marked with ‘+’ from V1 to Vp, P player losses the game finally. Also we can see, N player does the best to destory that kind of roads described above in rule(1).

Now give you such a graph, you need to verdict the result whether the P player can win the game. If true, print “Yes”, or “No”.

输入:

There are T cases. In the first line of each case, there are two intergers P and Q, P is the number of the vertexs and Q is the number of the edges. Then there come Q lines,each contains two integers v1(1 � P), and v2 ( 1 � P), indicating one edge between the vertex v1 and v2.
  T<=100,2<=P<=30,1<=Q<=1000.
  There is a blank line to separate the adjacent cases.

输出:

There are T cases. In the first line of each case, there are two intergers P and Q, P is the number of the vertexs and Q is the number of the edges. Then there come Q lines,each contains two integers v1(1 � P), and v2 ( 1 � P), indicating one edge between the vertex v1 and v2.
  T<=100,2<=P<=30,1<=Q<=1000.
  There is a blank line to separate the adjacent cases.

样例输入:

2
2 2
1 2
1 2

4 5
1 2
1 3
2 3
2 4
3 4

样例输出:

Yes
No


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  4. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。