首页 > ACM题库 > HDU-杭电 > hdu 3963 Sisters待解决[解题报告]C++
2015
04-14

hdu 3963 Sisters待解决[解题报告]C++

Sisters

问题描述 :

Mikoto(Railgun) is an excellent ESP(Extra Sensory Perception) girl with the dreadful skill Railgun in Academy City.
Microgene

But there is a bitter reality that Mikoto’s sisters are being massacred by Yuriko(Accelerator) for experiments.
Microgene

As Yuriko is the most powerful ESPer, what Mikoto can do is to destroy all related laboratories in Academy City to delay the massacre.

N Laboratories are connected by M wires and the power system can be considered to an undirected graph.

Academy City is divided into several districts.

If there are at least two non-intersecting paths between two laboratories, then the two cities belong to the same district.

Two paths are considered as non-intersecting paths if and only if there is no same edge in both of them.

If there are one wire connecting two laboratories of two different districts, then the two districts are neighbors. Power can be transported between neighbor districts.

Mikoto can destroy all laboratories in the district where she is by the Railgun, that costs K+X(X is the numbers of laboratories in this district) points energy. Mikoto can use the Railgun anywhere and any number of times.

What’s more, Mikoto generates electricity at the same time she shoot the Railgun. Mikoto can use the power to destroy all laboratories in other districts via wires. For any district to be attacked by electricity, the cost is f(n) points energy, and n is the number of districts (excluding the district where Mikoto shoot the Railgun) in the path from Mikoto to it. More specifically, if Mikoto have shot the Railgun destroying all laboratories in the district she chose, she can choose several other districts to be attacked by electricity she generate and the cost for each district is described above.

Now, the problem is the mininum cost to destroy all laboratories.

输入:

There are several test cases.

For each test case, the first line contains three integers, N(1 ≤ N ≤ 1000), M(1 ≤ M ≤ 1000000), K(1 ≤ K ≤ 1000000000).
Then, 2 to M + 1 lines, each line contain two different integers a and b (1 ≤ a,b ≤ N), meaning that there is a undirected wire between laboratories a and b.

Then, the M + 2 lines contain N-1 number, meaning f(1), f(2), … , f(n – 1). (0 ≤ f(1) ≤ f(2) ≤ … ≤ f(N – 1) ≤ 1000000000)

You can safely assume that all numbers in the input and output will in the range of 32-bit signed integer and all the laboratories are connected by wires.

Input is terminated by EOF.

输出:

There are several test cases.

For each test case, the first line contains three integers, N(1 ≤ N ≤ 1000), M(1 ≤ M ≤ 1000000), K(1 ≤ K ≤ 1000000000).
Then, 2 to M + 1 lines, each line contain two different integers a and b (1 ≤ a,b ≤ N), meaning that there is a undirected wire between laboratories a and b.

Then, the M + 2 lines contain N-1 number, meaning f(1), f(2), … , f(n – 1). (0 ≤ f(1) ≤ f(2) ≤ … ≤ f(N – 1) ≤ 1000000000)

You can safely assume that all numbers in the input and output will in the range of 32-bit signed integer and all the laboratories are connected by wires.

Input is terminated by EOF.

样例输入:

5 5 10
1 2
1 3
2 3
1 4
2 5
5 10 15 20
5 4 10
2 1
3 2
4 1
5 3
4 9 11 12

样例输出:

23
34


  1. 在方法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的边不是都没了吗?

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

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮