主题

主题

 
   

C15C:Rabbit's Festival

原题:http://poj.openjudge.cn/practice/C15C/

描述

Long long ago, there lived a lot of rabbits in the forest. Every rabbit lived in his own house and only meet each other in festival.

Let us consider the whole traffic network in the rabbit kingdom as a graph while the houses are nodes and the roads connected two houses are edges.

The festival would last for K days. For traffic congestion controlling reason, the i-th road would be closed on the Ci-th day (i.e. the rabbit cannot go through this road on the Ci-th day).

Now the rabbits want to calculate that how many pairs of rabbits are able to meet each other on the i-th day. Note that there lived exactly one rabbit in each house and two rabbits can meet each other if and only if there is a route between their houses which only consists non-closed road on that day.

输入

The input consists of at most 10 cases.

For each test case, the first line contains three integers N, M, K, which respectively indicate the number of houses, the number of roads and the number of days that the festival will last.

The next M lines describe this graph. For the i-th line, it contains three integer Xi, Yi, Ci, where Xi, Yi indicate the numbers of houses that the i-th road connect and Ci indicates the road would be close at the Ci-th day.

Houses are numbered from 1 to N. Roads are undirected and numbered from 1 to M. Days are numbered from 1 to K. 0 ≤ N, K ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ Xi, Yi ≤ N, Ci is positive. If Ci exceeds K, then this road will keep open during the whole festival.

输出

For each test case, output K lines. The i-th line contains only one integer indicating the number of rabbit pairs which are able to meet each other on the i-th day.

样例输入

7 8 4

1 2 4

1 3 3

3 4 2

3 6 2

5 3 1

4 5 1

5 6 1

7 6 3

样例输出

15

21

7

15


题目大意:

(刚开始看错了题目,尴尬……以为“there is a route”指的是“there is only one route”的意思,后来反复读来读去觉得应该是“存在”不是“仅有一条”)。

给出n个点m条边的无向图,每条边有一个消失的时刻。求每个时刻可以连通的点对的个数。


个人解法:

一个很普通的题目。

我们按照时间分治。由于我们记录的是消失的时刻,那么当递归左边的时候就把右边的边插入,反则把左边的边插入。

然后回溯的时候撤销即可。用并查集即可实现。

对于统计答案,我们只需要知道连通块的大小。在连边以及撤销的时候可以维护。


代码如下:

https://code.csdn.net/snippets/2276970


本来还愁不让提交……结果一看通过的人发现了张翼德和关云长……果断vjudge。

 
 
评论