月度归档:2017年12月

BZOJ 1305: [CQOI2009]dance跳舞(二分+最大流)

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

Input

第一行包含两个整数n和k。以下n行每行包含n个字符,其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

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

因为时间有序,我们可以按照时间分治,对于区间[L,M]的时刻,我们先把[M+1,R]的点并查集连起来,然后这样递归下去直到L=R,那么就可以求出这个时刻的答案。然后一步步撤销回去,递归处理[M+1,R]的点的时候,先把[L,M]的点全部加入,因为已经处理过了。。。
时间复杂度应该是O(nlognlogn)的。。。

hihocoder 1629 : Graph(带撤销并查集+莫队)

时间限制:4000ms
单点时限:4000ms
内存限制:256MB
描述
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。。。