社区讨论
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 条回复,欢迎继续交流。
正在加载回复...