Construction of a tree[AGC029F]

发表于 分类于 ，

题意

给定 $n-1$ 个点集(全集为 ${1,2,\cdots,n}$)，从每个集合内选两个点连边，使得最后形成一棵树。输出方案。

$n\leq 10^5$，点集大小之和 $\le 2\times 10^5$。

链接

AtCoder

题解

对于这 $n-1$ 个集合 $S={S_1,S_2\cdots S_{n-1}}$，我们选出这些集合的若干个子集 $T\subseteq S$，设 $f(T)$ 表示在 $T$ 中的集合 $S_i$ 所拥有的点的集合的大小。那么如果存在一个非空集合 $T$ 使得 $f(T)\leq |T|$，这 $f(T)$ 个点最多连出 $f(T)-1$ 条边，而 $f(T)-1< |T|$，显然不可能符合题意。

也就是说，$\forall T\subseteq S,|T|>0$，满足 $f(T)>|T|$ 是有解的必要条件。

发现这个很像Hall定理的形式：$f(T)\geq T$。

考虑构造一个二分图，左边是原图中的 $n$ 个点，右边是 $n-1$ 个集合，每个点如果在某个集合内则连一条边。

然后跑一个二分图匹配，不存在完美匹配则不满足Hall定理，则一定无解。

那么左边的点就有且仅有一个点没有匹配上，设这个点为 $x$。

考虑构造，对当前的 $x$ 进行dfs，找到与其相连的还未被标记的一个集合 $w$，然后标记它，再对这个集合 $w$ 找到与其匹配的点 $y$，则 $(x,y)$ 这条边就是集合 $w$ 中的边了。

构造的正确性证明：

我们只需说明不会出现有解的在这种构造下变为无解。按照这种方法，当无解的时候，当前被标记的集合所形成的的集合满足 $f(T)\leq |T|$ ，而有解的时候是不会有这种情况的。得证。

在二分图下跑Dinic，时间复杂度 $O(n\sqrt{m})$。

程序

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())

const int N=200010;
const int M=2000000;
namespace Dinic{
	const int inf=2e9;
	int s,t;
	int head[N],cur[N],ne[M],ver[M],val[M],tot=1;
	int d[N];
	queue<int> q;
	inline void add(int x,int y,int v)
	{
		ver[++tot]=y; val[tot]=v; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; ne[tot]=head[y]; head[y]=tot;
	}
	inline bool bfs()
	{
		fo(i,0,t) cur[i]=head[i];
		for(;!q.empty();q.pop());
		fo(i,0,t) d[i]=-1; q.push(s); d[s]=0;
		for(int u,v;!q.empty();)
		{
			u=q.front(); q.pop();
			for(int i=head[u];i;i=ne[i])
				if(val[i]&&d[v=ver[i]]==-1)
				{
					d[v]=d[u]+1,q.push(v);
					if(v==t) return 1;
				}
		}
		return 0;
	}
	int dfs(int u,int flow)
	{
		if(!flow||u==t) return flow;
		int res=flow,r,v;
		for(int &i=cur[u];i;i=ne[i])
			if(val[i]&&d[v=ver[i]]==d[u]+1)
			{
				r=dfs(v,min(res,val[i]));
				if(!r) continue;
				val[i]-=r; val[i^1]+=r;
				res-=r; if(!res) break;
			}
		return flow-res;
	}
	int dinic()
	{
		int flow=0;
		while(bfs()) flow+=dfs(s,inf);
		return flow;
	}
}
using namespace Dinic;
int n;
int X[N],Y[N],cnt;
bool vis[N];
void dfs(int u)
{
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=s&&!vis[v-n])
		{
			vis[v-n]=1;
			for(int j=head[v];j;j=ne[j])
				if(val[j])
					cnt++,X[v-n]=u,Y[v-n]=ver[j],dfs(ver[j]);
		}
}
int main()
{
	n=read();
	Dinic::t=2*n;
	s=0; t=2*n;
	ff(i,n+1,2*n) CASET add(read(),i,1);
	fo(i,1,n) add(s,i,1);
	ff(i,n+1,2*n) add(i,t,1);
	if(dinic()!=n-1) return puts("-1")&0;
	int root;
	for(int i=head[0];i;i=ne[i]) if(val[i]) root=ver[i];
	dfs(root);
	if(cnt!=n-1) return puts("-1")&0;
	ff(i,1,n) printf("%d %d\n",X[i],Y[i]);
	return 0;
}