首页 > ACM题库 > HDU-杭电 > hdu 2667 SpaceStation待解决[解题报告]C++
2014
02-12

hdu 2667 SpaceStation待解决[解题报告]C++

SpaceStation

问题描述 :

N space stations are built in the space, and flights should be set among these space stations. Flights are bidirectional, and connect different space stations. A valid arrangement of flights must satisfy the rules below:
1. Every space station can be reached from all others via flights directly or indirectly.
2. Because the spaceships are too expensive, the number of flights should be minimal.
3. Due to the limited resource of service and communication, the number of flights directly connected to each space station is limited.
Here comes the problem: how many different valid arrangements can be set?
Two arrangements A and B are different means that, there exists at least one flight in A but not in B, or there exists at least one flight in B but not in A.

输入:

The input contains multiple test cases.
The first line contains an integer T, 0 < T <= 20, representing the number of test cases.
For each test case:
The first line contains an integer N, 0 < N <= 300, representing the number of space stations. The second line contains N integers K1、K2 ? KN, 0 <= Ki <= N – 1,Ki, separated by blanks, representing the maximal flights directly connected to the i-th space station.

输出:

The input contains multiple test cases.
The first line contains an integer T, 0 < T <= 20, representing the number of test cases.
For each test case:
The first line contains an integer N, 0 < N <= 300, representing the number of space stations. The second line contains N integers K1、K2 ? KN, 0 <= Ki <= N – 1,Ki, separated by blanks, representing the maximal flights directly connected to the i-th space station.

样例输入:

2 
4 
2 2 2 2 
4 
3 3 3 3 

样例输出:

12 
16 


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish