题解 AT4505 【[AGC029F] Construction of a tree】

· · 题解

AGC 029F

Solution

神仙构造题。

考虑如何才能构成一颗树，显然有一个必要条件是对于每个点u，整张图除去u之外的所有点和点集存在完美匹配，具体来说就是考虑以u为根，去掉u之后剩余每个点和他的父亲对应的那条边可以刚好构成完美匹配（即考虑一张二分图左边是除了u之外的点，右边是E_i，u和E_i连边当且仅当u\in E_i，该图存在完美匹配）。用Hall定理来表达就是，设S为\{E_1,E_2\cdots E_n\}的任意一个子集，N(S)表示这些E_i中的点的并集，则|N(S)|\geq |S|+1。

实际上这个条件也是充分的，证明考虑如下的构造算法：首先将1去除后求出完美匹配，然后从1开始BFS，每次选择一条左边点u到右边点v的边，然后找到v的匹配点p_v，若这两个点都没有被访问过，则添加一条树边(u,p_v)。于是上面的命题等价于这样搜索能够遍历所有的点。因为如果某一个时刻不能走到未走过的点，那么走过的左边点个数比右边点个数多1，所以左边点总个数比右边点总个数多1，故现在未遍历的右边的点的集合T满足N(T)\leq T，与上面Hall定理矛盾。而如果上面的命题不成立，显然无法搜出合法的方案，而这样搜索能遍历所有的点等价于原问题有解，故原命题等价于原问题有解。

时间复杂度\mathcal O(\sum|E_i|\sqrt n)

Code

int n,tot,S,T;
int p[MAXN];
pii ans[MAXN];
vector<int> G[MAXN];

namespace NetWorkFlow{
    int len,maxFlow;
    int head[MAXN],cur[MAXN],dep[MAXN],vis[MAXN];
    queue<int> q;

    struct Edge{
        int to,next,flow;
    } e[MAXM];

    void Init(){
        memset(head,-1,sizeof(head));
        len = 1;
    }

    void add_edge(int u,int v,int flow){
        e[++len] = (Edge){v,head[u],flow};
        head[u] = len;
        e[++len] = (Edge){u,head[v],0};
        head[v] = len;
    }

    int bfs(){
        for(int i = 0;i <= tot;i++){
            cur[i] = head[i];
            dep[i] = -1;
        }
        dep[S] = 0;
        q.push(S);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i = head[u];i != -1;i = e[i].next){
                int v = e[i].to;
                if(dep[v] == -1 && e[i].flow){
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[T] != -1;
    }

    int dfs(int u,int flow){
        if(u == T){
            maxFlow += flow;
            return flow;
        }
        int used = 0,low;
        for(int i = cur[u];i != -1;i = e[i].next){
            cur[u] = i;
            int v = e[i].to;
            if(dep[v] == dep[u] + 1 && e[i].flow){
                if(low = dfs(v,min(flow - used,e[i].flow))){
                    e[i].flow -= low;
                    e[i ^ 1].flow += low;
                    used += low;
                    if(used == flow)
                        break;
                }
            }
        }
        return used;
    }

    int Dinic(){
        while(bfs()) dfs(S,INF);
        return maxFlow;
    }

    bool GetAns(){
        for(int u = 2;u <= n;u++){
            for(int i = head[u];i != -1;i = e[i].next){
                int v = e[i].to;
                if(v != S && !e[i].flow) p[v - n] = u;
            }
        }
        q.push(1);
        int cnt = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v : G[u]){
                if(!vis[v]){
                    ans[v] = make_pair(u,p[v]);
                    cnt += 1;
                    q.push(p[v]);
                    vis[v] = 1;
                }
            }
        }
        return cnt == n - 1;
    }
}

int main(){
    NetWorkFlow::Init();
    scanf("%d",&n);
    S = 1;
    for(int i = 2;i <= n;i++)
        NetWorkFlow::add_edge(S,i,1);
    for(int i = 1,x,y;i < n;i++){
        scanf("%d",&x);
        while(x--){
            scanf("%d",&y);
            if(y != 1) NetWorkFlow::add_edge(y,i + n,1);
            G[y].push_back(i);
        }
    }
    tot = T = n + n;
    for(int i = 1;i < n;i++)
        NetWorkFlow::add_edge(i + n,T,1);
    if(NetWorkFlow::Dinic() < n - 1){
        puts("-1");
        return 0;
    }
    if(!NetWorkFlow::GetAns()){
        puts("-1");
        return 0;
    }
    for(int i = 1;i < n;i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}