# BZOJ 1305: [CQOI2009]dance跳舞（二分+最大流）

Description

Input

Output

Sample Input

3 0

YYY

YYY

YYY

Sample Output

3
HINT

N<=50 K<=30 一开始没有想到二分，直接跑网络流，然后发现这样没法体现n对人一起跳舞的限制。 建图：把每个人拆点为i和i+n，以及i+2*n,i+3*n分别表示男生，男生不喜欢，女生，女生不喜欢。拆点之间连容量为K的边，因为最多只能和K个不喜欢的人跳舞。根据矩阵进行连边，然后源点向男生连容量为mid的边，女生向汇点连容量为mid的边这样可以保证每次都是n对的话，那么最大流的答案一定要大于等于mid*n才可以。

# OpenJudge C15C-Rabbit’s Festival（CDQ+带撤销并查集）

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.

Input
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.
Output
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.
Sample Input
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
Sample Output
15
21
7
15

# hihocoder 1629 : Graph（带撤销并查集+莫队）

The country contains N cities numbered from 1 to N and M undirected roads connecting pairs of cities. There are some queries. Each query is represented by two numbers: L and R , meaning that all the cities whose number is between L and R(L and R are included) are safe, and other cities are not safe. We define city A can reach city B if and only if they are both safe and there exists a path from A to B that the cities on the path are all safe.

For each query, you need to figure out the number of pairs of cities that can reach each other under the condition given by the query.

First line contains one number T which means the number of test cases.

For each test case, first line contains three numbers, above mentioned N , M and Q.

Next M lines, each line contains two integers: X, Y (X != Y) which means there is a road between city X and city Y (1 <= X,Y <= N). Next Q lines, each line contains two numbers: L, R which indicates an query(1 <= L,R <= N, L <= R). T <= 5, N , M <= 50000, Q <= 100000 输出 For each test case, output Q lines, each line contains the answer of the correspondent query. 样例输入 1 6 6 4 1 2 2 3 2 6 1 5 2 4 4 5 1 4 3 6 2 6 3 4 样例输出 6 1 10 0\\ 为了准备ec，为了圆北京赛区时的一个梦想，把这个题补了。。。。但是写出了1w个bug，还被卡常数。。。 直接说做法：把所有的m条边按照属于1号点2号点这样的顺序排序，因为是无向图所以得到了一个长度为2m的序列。然后在这个上面把所有询问跑莫队。考虑如何维护答案，我们可以把询问左端点在相同的一块放到一起处理，这时候右端点单调递增，我们先不考虑左端点在的那一块中的边，而是把从那块之后的第一条边到右端点的所有边依次加入并查集。然后左边那部分是可以撤销的，所以只要并查集支持带撤销就可以维护答案了。。。 复杂度就是2msqrt(2m)logn了。。。 很多人都是对点分块我表示理解不能，这样复杂度不对啊好不好QAQ。。。