正題

題目鏈接:https://www.luogu.com.cn/problem/CF786E

---

題目大意

$n$個點的一棵樹，$m$個人每個人走一個路徑。

給一些人狗或者一些邊狗每個人要求要么它自己有狗要么它走的路徑上都有狗。

---

解題思路

考慮最小割，其實就是要么割一個人要么割一整條路徑，然后倍增優化連邊即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=21000,inf=2147483647/3; struct node{int to,next,w; }a[N*20]; int s,t,cnt,n,m,tot,f[N][20],p[N][20],vi[N],ls[N],dep[N],z[N]; struct net_flow{node a[N*400]; int tot=1,ls[N*20],dep[N*20],out[N*20];queue<int> q;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(){memset(dep,0,sizeof(dep));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=ls[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(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return flow;}if(!rest)dep[x]=1;return rest;}void get_netf(){int ans=0;while(bfs())ans+=dinic(s,inf);printf("%d\n",ans);ans=0;for(int x=1;x<=m;x++)if(!dep[vi[x]])out[++ans]=x;printf("%d",ans);for(int i=1;i<=ans;i++)printf(" %d",out[i]);putchar('\n');ans=0;for(int x=2;x<=n;x++)if(dep[p[x][0]])out[++ans]=z[x];printf("%d",ans);for(int i=1;i<=ans;i++)printf(" %d",out[i]);putchar('\n');} }nf; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){p[x][0]=++cnt;if(x!=1)nf.addl(cnt,t,1);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==f[x][0])continue;f[y][0]=x;z[y]=(i+1)/2;dep[y]=dep[x]+1;dfs(y);} } void add_path(int pos,int x,int y){if(dep[x]>dep[y])swap(x,y);for(int i=15;i>=0;i--)if(dep[f[y][i]]>=dep[x])nf.addl(pos,p[y][i],inf),y=f[y][i];if(x==y)return;for(int i=15;i>=0;i--)if(f[x][i]!=f[y][i]){nf.addl(pos,p[x][i],inf);nf.addl(pos,p[y][i],inf);x=f[x][i];y=f[y][i];}nf.addl(pos,p[x][0],inf);nf.addl(pos,p[y][0],inf);return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}s=++cnt;t=++cnt;dep[1]=1;dfs(1);for(int j=1;j<16;j++)for(int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];p[i][j]=++cnt;nf.addl(p[i][j],p[i][j-1],inf);nf.addl(p[i][j],p[f[i][j-1]][j-1],inf);}for(int i=1;i<=m;i++){vi[i]=++cnt;int x,y;scanf("%d%d",&x,&y);nf.addl(s,vi[i],1);add_path(cnt,x,y);}nf.get_netf(); }

總結

以上是生活随笔為你收集整理的CF786E-ALT【网络流,倍增】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。