OI题解 - Construction of a tree(AtCoder)

这道题好有意思啊（感觉构造题的方法都特别神奇）

# 题意

有 $n$ 个点（1到n）和 $n-1$ 个点集（$E_1$到$E_{n-1}$），要从每个点集中选出两个不同的点，并将这两个点连边。

是否存在一种选取点的方案使得 $n$ 个点与所连的边构成一棵树，如果存在，输出任意一种方案。

数据规模：$2\le n\le10^5$；$|E_i|>1$；$\sum |E_i|\le2\times10^5$

# 解析

考虑这样建图：图上的 $n$ 个点作为二分图的甲部，$n-1$ 个集合每个集合建一个点，作为乙部；如果点 $i$ 在集合 $E_j$ 中，那么它们之间在二分图上存在一条边。

就有一个结论：“将甲部任意一个点删除后，二分图有完全匹配”是“可以构成树”的充要条件。

> 证明

必要条件（如果“可以构成树”，则满足该条件）：

不难发现其实 $n-1$ 个集合就是 $n-1$ 条边。
假设删除的甲部的点为 $u$；如果“可以构成树”，那么把 $u$ 作为这棵树的根，整棵树就会变成下面这样：

于是每个点与它上面的边匹配，就可以形成完全匹配。

充分条件（如果满足该条件，则“可以构成树”）：
考虑在该条件下如何构造一棵树。

先取点 $1$ 作为树根，然后把 $1$ 从二分图中删掉，求一个完全匹配；找到任意一个包含 $1$ 的集合 $E_i$，设完全匹配中与 $E_i$ 匹配的点为 $u$，就连边 $(1,u)$。树的点集 $S=\{1,u\}$ 。

在二分图中删除 $u,E_i$。显然二分图仍然存在完美匹配。

求完全匹配，找到一个包含 $S$ 中任意一个点 $x$ 的集合 $E_j$，设完全匹配中与 $E_j$ 匹配的是点 $v$；连边 $(x,v)$。树的点集 $S=\{1,u,v\}$。

在二分图中删除 $v,E_j$。

……（直到删完所有点）

虽然时间复杂度并不允许我们枚举删除一个点，判断是否有完美匹配；但是利用这个结论，可以先删除点 $1$，然后求完美匹配——如果 $u$ 与 $E_i$ 匹配就把 $u$ 与 $E_i$ 中的所有点（除了本身）连边，并且给这些边打上 $E_i$ 的标记（这样才能判断连的边是哪一个点集形成的）。

然后从 $1$ 开始 DFS，每种标记的边只能走一条（每个集合只提供一条边）、每个点只能经过一次（树）。如果能够遍历所有点，那么 DFS树 就是一个解；否则无解。

# 源代码

/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5,INF=(1<<29),SZ=2*N+10;

struct EDGE{
    int to,cap;
    EDGE *nxt,*rev;
    EDGE(){}
    EDGE(int _t,int _c,EDGE *_n,EDGE *_r):to(_t),cap(_c),nxt(_n),rev(_r){}
};
struct GRAPH{
    EDGE edg[4*N*2+10],*head[SZ],*ncnt;
    GRAPH(){ncnt=edg;}
    void AddEdge(int u,int v,int cap){
        EDGE *p=++ncnt,*q=++ncnt;
        *p=EDGE(v,cap,head[u],q);head[u]=p;
        *q=EDGE(u,  0,head[v],p);head[v]=q;
    }
    EDGE* operator [](int id){return head[id];}
};
GRAPH Gr;
EDGE *cop[SZ];
int dis[SZ];
vector< pair<int,int> > lnk[N+3];
int n,S,T,tot;
vector<int> tset[N+3];
int ans[N+3][2];
bool vis[N+3];

int Aug(int u,int in){
    if(u==T) return in;
    int out=0;
    while(cop[u]){
        EDGE *it=cop[u];cop[u]=cop[u]->nxt;
        int v=it->to;
        if(dis[v]!=dis[u]+1 || it->cap<=0) continue;
        int tov=Aug(v,min(in-out,it->cap));
        it->cap-=tov;it->rev->cap+=tov;
        out+=tov;
        if(out==in) break;
    }
    return out;
}
bool BFS(){
    for(int i=1;i<=T;i++) dis[i]=-1,cop[i]=Gr[i];
    queue<int> que;que.push(S);dis[S]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(EDGE *it=Gr[u];it;it=it->nxt){
            int v=it->to;
            if(dis[v]!=-1 || it->cap<=0) continue;
            dis[v]=dis[u]+1;
            if(v==T) return true;
            que.push(v);
        }
    }
    return false;
}
int Dinic(){
    int res=0;
    while(BFS())
        res+=Aug(S,INF);
    return res;
}
void DFS(int u){
    vis[u]=true;tot++;
    for(int i=(int)lnk[u].size()-1;i>=0;i--){
        int v=lnk[u][i].first,id=lnk[u][i].second;
        if(ans[id][0] || vis[v]) continue;
        ans[id][0]=u;ans[id][1]=v;
        DFS(v);
    }
}
int main(){
    // freopen("input.txt","r",stdin);
    scanf("%d",&n);
    S=n*2;T=S+1;
    for(int i=2;i<=n;i++) Gr.AddEdge(S,i,1);
    for(int i=1;i<n;i++) Gr.AddEdge(i+n,T,1);
    for(int i=1;i<n;i++){
        int num;scanf("%d",&num);
        while(num--){
            int u;scanf("%d",&u);
            Gr.AddEdge(u,n+i,1);
            tset[i].push_back(u);
        }
    }
    int res=Dinic();
    if(res<n-1) printf("-1\n");
    else{
        for(int i=1;i<n;i++){
            int E=i+n,u=-1;
            for(EDGE *it=Gr[E];it && u==-1;it=it->nxt)
                if(it->cap)
                    u=it->to;
            for(int j=(int)tset[i].size()-1;j>=0;j--)
                if(tset[i][j]!=u){
                    int v=tset[i][j];
                    lnk[u].emplace_back(v,i);
                    lnk[v].emplace_back(u,i);
                }
        }
        DFS(1);
        if(tot<n) printf("-1\n");
        else
            for(int i=1;i<n;i++)
                printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

The End

Thanks for reading!

你看我今天更博客这么勤奋，是不是可以开始咕了？