社区讨论

TLE :(((( how?

AT_agc029_f[AGC029F] Construction of a tree参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m07hzdm3
此快照首次捕获于
2024/08/24 10:04
2 年前
此快照最后确认于
2025/11/04 22:35
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+1145,M=1e6+1145;
const int INF = 0x3f3f3f3f;
int n;
int first[M],idx=1;
struct edge {
	int d,ne,f;
} ed[M];
void add_edge(int e,int d,int f) {
	idx++,ed[idx].f=f,ed[idx].d=d,ed[idx].ne=first[e],first[e]=idx;
	idx++,ed[idx].f=0,ed[idx].d=e,ed[idx].ne=first[d],first[d]=idx;
}
int S,T,dis[M],cur[M],edt;

int Q[N],l,r;
int bfs() {
	for(int i=0;i<=edt;i++) dis[i]=0;
	dis[S]=1;
	l=1,r=0;
	Q[++r]=S;
	cur[S]=first[S];
	while(l<=r) {
		int t=Q[l++];
		for(int i=first[t]; i; i=ed[i].ne) {
			int d=ed[i].d;
			if(!dis[d]&&ed[i].f) {
				dis[d]=dis[t]+1;
				cur[d]=first[d];
				Q[++r]=d;
			}
		}
	}
	return dis[T];
}
int dfs(int x,int lim) {
	if(T==x || !lim) return lim;
	int res=0;
	for(int &i=cur[x]; i; i=ed[i].ne) {
		int d=ed[i].d;
		if(dis[d]==dis[x]+1&&ed[i].f!=0) {
			int fl=dfs(d,min(lim,ed[i].f));
			if(fl) {
				ed[i].f-=fl,ed[i^1].f+=fl,res+=fl,lim-=fl;
				if(!lim) return res;
			} else dis[d]=0;
		}
	}
	return res;
}
int dinic() {
	int sum=0;
	while(bfs()) sum+=dfs(S,INF);
	return sum;
}
int PT;
bool vis[M];
pair<int,int> ANS[M];
int DFS(int now) {
	for(int i=first[now]; i; i=ed[i].ne) {
		if(vis[ed[i].d]||ed[i].d==S) continue;
		vis[ed[i].d]=1;
		for(int j=first[ed[i].d]; j; j=ed[j].ne) {
			if(ed[j].f) {
				ANS[++PT]= {now,ed[j].d};
//				cout<<ed[j].f<<" "<<now<<" "<<ed[j].d<<endl;
				DFS(ed[j].d);
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<n; i++) {
		int t;
		scanf("%d",&t);
		while(t--) {
			int awa;
			scanf("%d",&awa);
			add_edge(awa,i+n,1);
		}
	}
	edt=n*2-1;
	S=++edt;
	T=++edt;
	for(int i=1; i<=n-1; i++) add_edge(S,i,1),add_edge(i+n,T,1);
	add_edge(S,n,1);
	if(dinic()!=n-1) {
		puts("-1");
		return 0;
	}
	int rt=1;
	for(int i=first[S]; i; i=ed[i].ne) if(ed[i].f) rt=ed[i].d;
	PT=1;
	DFS(rt);
	if(PT==n) {
		for(int i=2; i<=n; i++) printf("%d %d\n",ANS[i].first,ANS[i].second);
	} else puts("-1");

	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...