「CodeForces-1252L」Road Construction(二分图最大匹配)

发表于 | 分类于 ， ，

L - Road Construction
给定一棵基环树上的边，每一条边可以被指定类的工人维修，求能使树上点联通的维修方案

题意

给定一棵基环树上的边，每一条边可以被指定类的工人维修，求能使树上点联通的维修方案。

题解

如果对于边和工人一一连边，边数可能达到$NK$，考虑简化边数。

对于每组边对应的类型数$M_i$，有$\sum_{i=1}^n M_i<=10000$，所以让树边与工人类型数连边，并对每种类型的工人计数，连向汇点即可。

对于一棵基环树，要选$n-1$条边使其联通，假设其环上有k条边，必须选择“环上的k-1条边”和“环外的所有边”。dfs求出基环树上的环，存储“环外的边”为A集合，“环上的边”为B集合。

首先对起点向A集合中的点连边，判断是否全部匹配；再对起点向B集合中的点连边，判断总的流量是否$>=n-1$即可。

代码

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 2000 + 10;
const int maxm = 10000 + 10;
 
int n, k;
int pre[maxn], id[maxn];
int dfn[maxn], cnt;
vector<pair<int, int> > edge[maxn];
bool vis[maxn];
vector<int> A, B;
map<int, int> tag;
 
void dfs(int u)
{
	dfn[u] = ++ cnt;
	for(auto x : edge[u])
	{
		int v = x.first;
		if(v == pre[u]) continue;
		if(dfn[v])
		{
			if(dfn[v] < dfn[u]) continue;
			B.push_back(x.second);
			for(; v != u; v = pre[v]) B.push_back(id[v]);
			continue;
		}
		pre[v] = u;
		id[v] = x.second;
		dfs(v);
	}
}
 
const int MAX_V = 10000 + 2000 + 10;
const int inf = 0x3f3f3f3f;
int res[maxn];
 
struct Dinic
{
 
	struct edge{ int to, cap, rev; } ;
	vector<edge> G[MAX_V];
	int level[MAX_V];
	int iter[MAX_V];
 
	void add(int from, int to, int cap)
	{
		G[from].push_back((edge){to, cap, (int)G[to].size()});
		G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
	}
 
	void bfs(int s)
	{
		memset(level, -1, sizeof level);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while(!que.empty())
		{
			int v = que.front(); que.pop();
			for(int i = 0; i < G[v].size(); i ++)
			{
				edge &e = G[v][i];
				if(e.cap > 0 && level[e.to] < 0)
				{
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}	
		}
	}
 
	int dfs(int v, int t, int f)
	{
		if(v == t) return f;
		for(int &i = iter[v]; i < G[v].size(); i ++)
		{
			edge &e = G[v][i];
			if(e.cap > 0 && level[v] < level[e.to])
			{
				int d = dfs(e.to, t, min(f, e.cap));
				if(d > 0)
				{
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
 
	int max_flow(int s, int t)
	{
		int flow = 0;
		for(;;)
		{
			bfs(s);
			if(level[t] < 0) return flow;
			memset(iter, 0, sizeof iter);
			int f;
			while((f = dfs(s, t, inf)) > 0) flow += f;
		}
	}
 
	void getans()
	{
		for(int i = 1; i <= n; i ++)
		{
			for(auto e : G[i])
			{
				if(e.to <= n) continue;
				if(e.cap == 0) res[i] = e.to - n;
			}
		}
	}
}dinic;
 
vector<int> P[maxm];
int pos[maxm];
pair<int, int> e[maxn];
int ans[maxn];
 
int main()
{
	int tot = 0;
	scanf("%d%d", &n, &k);
	int S = 0, T;
	for(int i = 1; i <= n; i ++)
	{
		int u, k, x;
		scanf("%d%d", &u, &k);
		edge[i].push_back({u, i});
		edge[u].push_back({i, i});
		e[i] = make_pair(i, u);
		while(k --)
		{
			scanf("%d", &x);
			if(!tag[x]) tag[x] = ++ tot;
			dinic.add(i, tag[x] + n, 1);
		}
	}
	dfs(1);
	for(auto v : B) vis[v] = true;
	for(int i = 1; i <= n; i ++) if(!vis[i]) A.push_back(i);
	T = n + tot + 1;
	for(int i = 1; i <= k; i ++)
	{
		int x;
		scanf("%d", &x);
		if(!tag[x]) continue;
		P[tag[x]].push_back(i);
	}
	for(int i = 1; i <= tot; i ++) dinic.add(n + i, T, (int)P[i].size());
	for(auto x : A) dinic.add(S, x, 1);
	int cur = dinic.max_flow(S, T);
	if(cur < A.size()) return 0 * puts("-1");
	for(auto x : B) dinic.add(S, x, 1);
	cur += dinic.max_flow(S, T);
	if(cur < n - 1) return 0 * puts("-1");
	dinic.getans();
	for(int i = 1; i <= n; i ++)
	{
		if(pos[res[i]] == P[res[i]].size()) continue;
		ans[P[res[i]][pos[res[i]]]] = i;
		pos[res[i]] ++;
	}
	for(int i = 1; i <= k; i ++) 
	{
		if(ans[i] == 0) puts("0 0");
		else printf("%d %d\n", e[ans[i]].first, e[ans[i]].second);
	}
	return 0;
}