@description@
给定 N - 1 个 {1, 2, ..., N} 的子集，第 i 个为 Ei。
请构造 N - 1 条边 (u1, v1), (u2, v2), ... 使得 ui ∈ Ei 且 vi ∈ Ei，满足这 N - 1 条边构成一棵树。
@solution@
好神的题。
构造一个二分图，第 i 条边对应的点连向 Ei 中所有的点。
有解的一个充分条件是大小为 k 的边集合能够连到点集合大小 > k（否则肯定会连成环）。
注意到这个和 hall 定理挺像的。记 N(S) 表示 S 的邻集，hall 定理描述的是 |S| <= |N(S)| 等价于二分图有完美匹配，而上述充分条件为 |S| < |N(S)|。
如何把它和 hall 定理联系起来呢？如果我们把 N 个点任意去掉一个点，那么应该有 |S| <= |N(S)|。
也就是 N 个点每一个点都不是二分图的必需点，这样就能推出 |S| < |N(S)| 的结论。
跑个 dinic，左边右点。此时如果能从点 i 到达汇点 t，则 i 不是必需点。
也就是以 t 为根沿逆向边建一棵可到达 t 的生成树，如果 N 个点都在树上，则合法。
注意此时这棵生成树就是我们想要构造的树。可以发现 N 个点都在树上时 N-1 条边对应的点也在树上，而 N-1 条边一定只会和两条树边连通，就是这条边对应的两个端点。
@accepted code@
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
namespace FlowGraph{
const int MAXV = 2*MAXN;
const int MAXE = 10*MAXN;
const int INF = (1 << 30);
struct edge{
int to, flow, cap;
edge *nxt, *rev;
}edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt = edges;
void addedge(int u, int v, int c) {
edge *p = (++ecnt), *q = (++ecnt);
p->to = v, p->cap = c, p->flow = 0;
p->nxt = adj[u], adj[u] = p;
q->to = u, q->cap = 0, q->flow = 0;
q->nxt = adj[v], adj[v] = q;
p->rev = q, q->rev = p;
}
int s, t;
int fa[MAXV + 5], dis[MAXV + 5];
int que[MAXV + 5], hd, tl;
bool relabel() {
for(int i=s;i<=t;i++)
dis[i] = t + 5, cur[i] = adj[i];
dis[que[hd = tl = 1] = t] = 0;
while( hd <= tl ) {
int x = que[hd++];
for(edge *p=adj[x];p;p=p->nxt) {
if( dis[p->to] > dis[x] + 1 && p->rev->cap > p->rev->flow )
dis[p->to] = dis[x] + 1, fa[p->to] = x, que[++tl] = p->to;
}
}
return !(dis[s] == t + 5);
}
int aug(int x, int tot) {
if( x == t ) return tot;
int sum = 0;
for(edge *&p=cur[x];p;p=p->nxt) {
if( p->cap > p->flow && dis[p->to] + 1 == dis[x] ) {
int del = aug(p->to, min(tot - sum, p->cap - p->flow));
p->flow += del, p->rev->flow -= del, sum += del;
if( sum == tot ) break;
}
}
return sum;
}
int max_flow(int _s, int _t) {
int flow = 0; s = _s, t = _t;
while( relabel() )
flow += aug(s, INF);
return flow;
}
}
int a[MAXN + 5], b[MAXN + 5];
int main() {
int N; scanf("%d", &N);
for(int i=1;i<N;i++) {
int c; scanf("%d", &c);
for(int j=1;j<=c;j++) {
int w; scanf("%d", &w);
FlowGraph::addedge(N + i, w, 1);
}
}
int s = 0, t = N + N - 1 + 1;
for(int i=1;i<N;i++) FlowGraph::addedge(s, N + i, 1);
for(int i=1;i<=N;i++) FlowGraph::addedge(i, t, 1);
int f = FlowGraph::max_flow(s, t);
if( f == N - 1 ) {
FlowGraph::relabel();
for(int i=1;i<t;i++)
if( FlowGraph::dis[i] == t + 5 ) {
puts("-1");
return 0;
}
for(int i=1;i<N;i++) a[i] = FlowGraph::fa[N + i];
for(int i=1;i<=N;i++) b[FlowGraph::fa[i] - N] = i;
for(int i=1;i<N;i++) printf("%d %d
", a[i], b[i]);
}
else puts("-1");
}
@details@
我好菜啊。
这种判定性 + 构造性问题以后又有一种新的思路了：是否所有子集满足一定条件就合法。