首页 > ACM题库 > HDU-杭电 > hdu 3073 Mars Life Tree待解决[解题报告]C++
2014
03-01

hdu 3073 Mars Life Tree待解决[解题报告]C++

Mars Life Tree

问题描述 :

20XX, the lives, or fossils, more exactly, on the Mars, which is founded on a totally different life type to the Earth one are found by human beings. MLT, or Mars Life Tree, thought to be the breeder of all lives on the Mars is discovered as a fossil too, is proved there used to have extremely complex types of life.
There is an extremely huge MLT under the surface of the Mars, is not a real tree, but variety of carbon-based protein balls(called “node”) connected by neuron links(called “edge”), formed a tree like structure, which is peer-to-peer reachable and non-circled. However, scientist discovered that the MLT is able to grow and mutate from basically two nodes with one edge. The mutation refers that a node is able to mutate to another kind of node and, costs some energy. And the growing means that one node can reach out a new edge and grows a new node at the other end of the edge, of course spend energy. Luckily, the energy costs of every kind of mutation and growing are measured and calculated.
Since scientists found out that different shape of MLT may give a birth to different kinds of lives, they believe that the earliest two node, called roots, directly connect to an organ like a lair to bear lives, which is air-slaked and become untraceable in the fossil.
Assuming the MLT grows obeying the rule of costing least energy, your mission is find out the roots in the fossil, point out the initial status of these two nodes, and calculate the total energy may cost during the evolvement.

输入:

There may be multiple test cases.
There are two integers n (n<=1000) and m (m<=10) in the first line means the counts of nodes of the MLT, and counts of kinds of nodes.
There are n integers Ki (1<=Ki<=m) in the second line, figure out that the ith node is one of kind Ki.
Then followed two integers S1, S2, (1<=S1, S2<=m), shows the type of the two nodes at the beginning.
A m*m matrix U followed, for every element Uij (Uij<100) in row i column j, refers the mutate energy cost from type i to type j.
Then there are m numbers P1 … Pm (Pi<100), Pi refers the energy cost of reaching out a new edge and node end by type i.
Then n-1 lines follows, two integers in each line x, y, (1<=x, y<=n, x≠y) means that node i and j are connected by a edge.

输出:

There may be multiple test cases.
There are two integers n (n<=1000) and m (m<=10) in the first line means the counts of nodes of the MLT, and counts of kinds of nodes.
There are n integers Ki (1<=Ki<=m) in the second line, figure out that the ith node is one of kind Ki.
Then followed two integers S1, S2, (1<=S1, S2<=m), shows the type of the two nodes at the beginning.
A m*m matrix U followed, for every element Uij (Uij<100) in row i column j, refers the mutate energy cost from type i to type j.
Then there are m numbers P1 … Pm (Pi<100), Pi refers the energy cost of reaching out a new edge and node end by type i.
Then n-1 lines follows, two integers in each line x, y, (1<=x, y<=n, x≠y) means that node i and j are connected by a edge.

样例输入:

3 3
1 2 3
1 1
0 1 3
1 0 1
3 1 0
1 1 3
2 3
1 2

样例输出:

2
3


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  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. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?