正题

题目链接:https://www.luogu.com.cn/problem/AT4505

题目大意

给出\(n\)个点和\(n-1\)个点集\(U_i\)，每个点集中选择两个点连边使得该图是一棵树。求方案。

\(n\in[1,10^5],\sum_{i=1}^{n-1} |U_i|\in[1,2*10^5]\)

解题思路

冬令营上讲的题目，现在来写。（而且好像我记得课上讲的做法是\(bitset\)的，还是时间久了我记岔了？）

第一眼看上去直觉像是\(hall\)定理但还是不会。

hall定理：\(2*n\)个点的二分图匹配，如果满足任意\(k\)个点都连接了不少于\(k\)个点的话，那么这张图就有完全匹配。

先套一下试试，发现满足条件的图对于它的每个子图\(S\)满足该子图是一个森林。

换句话说对于任意一个\(U\)的集合\(T\)，\(G(T)\)表示选出的边连接的节点个数，那么一定有\(G(T)\geq |T|+1\)

回顾一下\(hall\)定理发现是不是很像。

可以先给每个点集选出一个各不同的点（也就是跑一次匹配），如果选不出来那么显然无解。

然后考虑另一个点的选择，从没有被选择的那个点入手，这个点可以选择任何一个包含它的点集连接出去，然后就从下一个点集开始，直到回溯回来选择下一个。如果最后能够遍历所有点就是合法的。

考虑一下正确性，如果它不能遍历所有点那么没有被遍历的点集\(T\)无论怎么连接外面，就一定有一个环不满足\(G(T)\geq |T|+1\)。如果它能遍历所有点，那么我们已经构造出一个方案，显然合法。

时间复杂度\(O(\sum_{i=1}^{n-1}|E|\sqrt n+n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=4e5+10,inf=1e9;

struct node{

	int to,next,w;

}a[N*2];

int n,s,t,tot=1,cnt,ans;

int ls[N],p[N],b[N],dep[N],cur[N];

queue<int> q;bool v[N];

void addl(int x,int y,int w){

	a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;

	a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;

	return;

}

bool bfs(){

	for(int i=1;i<=t;i++)

		cur[i]=ls[i],dep[i]=0;

	while(!q.empty())q.pop();q.push(s);

	dep[s]=1;

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=ls[x];i;i=a[i].next){

			int y=a[i].to;

			if(dep[y]||!a[i].w)continue;

			dep[y]=dep[x]+1;

			if(y==t)return 1;

			q.push(y);

		}

	}

	return 0;

}

int dinic(int x,int flow){

	if(x==t)return flow;

	int rest=0,k;

	for(int &i=cur[x];i;i=a[i].next){

		int y=a[i].to;

		if(dep[x]+1!=dep[y]||!a[i].w)continue;

		rest+=(k=dinic(y,min(a[i].w,flow-rest)));

		a[i].w-=k;a[i^1].w+=k;

		if(rest==flow)return rest;

	}

	if(!rest)dep[x]=0;

	return rest;

}

void dfs(int x){

	cnt++;

	for(int i=ls[x];i;i=a[i].next){

		int y=a[i].to;

		if(v[y])continue;

		b[y]=x;v[y]=1;dfs(p[y]);

	}

}

int main()

{

	scanf("%d",&n);s=2*n;t=s+1;

	for(int i=1;i<n;i++){

		int m;scanf("%d",&m);

		for(int j=1;j<=m;j++){

			int x;scanf("%d",&x);

			addl(x,i+n,1);

		}

	}

	for(int i=1;i<=n;i++)addl(s,i,1);

	for(int i=1;i<n;i++)addl(i+n,t,1);

	while(bfs())

		ans+=dinic(s,inf);

	if(ans<n-1)return puts("-1")&0;

	for(int x=n+1;x<s;x++)

		for(int i=ls[x];i;i=a[i].next)

			if(a[i].w){p[x]=a[i].to;break;}

	v[s]=1;

	for(int i=ls[s];i;i=a[i].next)

		if(a[i].w)dfs(a[i].to);

	if(cnt<n)return puts("-1")&0;

	for(int x=n+1;x<s;x++)

		printf("%d %d\n",p[x],b[x]);

	return 0;

}

巴特西

AT4505-[AGC029F]Construction of a tree【构造题,hall定理,网络流】

正题

题目大意

解题思路

code

最新文章

热门文章