I. Interesting Computer Game ↬\looparrowright

题目描述

Apollo is playing an interesting computer game. There are nn rounds in the game.
At each round, the computer will give Apollo two integers aia_i and bib_i, and Apollo can do exactly one of the following three actions.
Apollo can do nothing.
If integer aia_i has not been selected in all previous rounds, Apollo can select integer aia_i.
If integer bib_i has not been selected in all previous rounds, Apollo can select integer bib_i.
Apollo has cracked the game, and he has known all the candidate numbers of each round before the game starts. Now he wants to know the maximum number of integers he can select with the optimal strategy.
I believe it would be very simple question for you, please help Apollo solve this question.

输入描述

The first line is an integer TT (1⩽T⩽10)(1 \leqslant T \leqslant 10), which is the number of test cases.
Each test case begins with a line containing a positive integer nn (1⩽n⩽105)(1 \leqslant n \leqslant 10^5), indicating the number of rounds in this game.
Then nn lines follow. The ii-th line contains two integers aia_i and bib_i (1⩽ai⩽109,1⩽bi⩽109)(1 \leqslant a_i \leqslant 10^9, 1 \leqslant b_i \leqslant 10^9), indicating that two integers of the ii-th round.

输出描述

For each test case, output one line containing Case #x: yCase\ \#x:\ y, where xx is the test case number and yy is the answer.

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
6
1 2
2 3
3 4
1 4
1 3
2 4
5
1 2
1 2
1 3
2 3
5 6

输出

1
2
Case #1: 4
Case #2: 4

分析

考虑用网络最大流解决。
aia_i 和 bib_i 组成一个二元组，每个二元组至多只能选取其中的一个数字；为了体现这种限制，可以设置 nn 个点，编号为 1∼n1\sim n，第 ii 个点有两条边分别连向二元组 (ai,bi)(a_i,b_i) 的两个数，容量为 11。每个数字至多被选取一次，将所因此要将所有二元组的数据离散化后，得到 cntcnt 个不同的数字，设为 cntcnt 个点，编号为 n+1∼n+cntn+1\sim n+cnt；接着，将代表二元组的 nn 个点向对应的两个数连边。源点向 nn 个表示二元组的点连边，容量为 11；cntcnt 个表示数据的点向 汇点连边，容量为 11。
按照上述方式建图，满足：每次至多选 (ai,bi)(a_i,b_i) 中的一个数字，已选的数字不会再选，网络最大流即为答案。由于边的容量为 11，因此当一条边在增广路上时，这条边的容量就被修改为 00；且按照图的结构，残量网络的层数较少；基于以上，虽然 Dinic\text{Dinic} 算法的最坏时间复杂度为 O(n2m)O(n^2m)（nn 为点数，mm 为边数），但是远远达不到这一上限，在 2s2s 的时限内是可以通过的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第八场） Problem I
Date: 9/1/2020
Description: Maximum Flow
*******************************************************************/
#include<iostream>
#include<queue>
#include<unordered_map>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100006;
const int inf=0x3f3f3f3f;
int C,_;
int cnt;
unordered_map<int,int>X;
struct E
{
	int to;
	int cap;
	int Next;
}edge[N*22];
int head[N<<2],tot;
int s,t;//源点 汇点
int depth[N<<2];
int a[N],b[N];
int n;
inline void add_edge(int,int,int);
bool bfs();
int dfs(int,int);
int Dinic();
int main(){
	//s=0 源点
	//1~n 每个二元组 限制流出为1
	//n+1~n+cnt 各个数字
	//t=n+cnt+1 汇点
	for(cin>>_;_;_--){
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++){
			scanf("%d%d",a+i,b+i);
		}
		cnt=0;
		X.clear();
		//离散化
		for(i=1;i<=n;i++){
			if(!X.count(a[i])){
				X[a[i]]=++cnt;
			}
			if(!X.count(b[i])){
				X[b[i]]=++cnt;
			}
		}
		//建图
		s=0;
		t=n+cnt+1;
		tot=1;
		memset(head,-1,sizeof(head));
		for(i=1;i<=n;i++){
			//源点流向n个二元组
			add_edge(s,i,1);
		}
		for(i=1;i<=n;i++){
			//每个二元组两个点
			add_edge(i,X[a[i]]+n,1);
			add_edge(i,X[b[i]]+n,1);
		}
		for(i=1;i<=cnt;i++){
			//所有数字连向汇点
			add_edge(i+n,t,1);
		}
		printf("Case #%d: %d\n",++C,Dinic());
	}
	return 0;
}
inline void add_edge(int u,int v,int cap){
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].Next=head[u];
	head[u]=tot;
	//建立反边
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool bfs(){
	memset(depth,0,sizeof(depth));
	queue<int>q;
	q.push(s);
	depth[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next){
			int y=edge[i].to;
			//残量网络上构建分层图
			if(edge[i].cap&&!depth[y]){
				q.push(y);
				depth[y]=depth[x]+1;
				if(y==t) return 1;//汇点可达
			}
		}
	}
	return 0;
}
int dfs(int x,int flow){//当前节点 当前流量
	//dfs 返回残量网络上可增广的流量
	if(x==t){
		return flow;
	}
	int rest=flow;//rest 剩余流量
	int temp;
	for(register int i=head[x];~i&&rest;i=edge[i].Next){
		int y=edge[i].to;
		if(edge[i].cap&&depth[y]==depth[x]+1){
			temp=dfs(y,min(rest,edge[i].cap));
			if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
			edge[i].cap-=temp;
			edge[i^1].cap+=temp;
			rest-=temp;
		}
	}
	return flow-rest;
}
int Dinic(){
	int maxflow=0;
	while(bfs()){
		maxflow+=dfs(s,inf);
	}
	return maxflow;
}