首页 > 代码库 > BZOJ 4390 Max Flow
BZOJ 4390 Max Flow
同运输计划。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 50050 #define maxe 100500 using namespace std; struct edge { int v,nxt; }e[maxe]; int n,k,x,y,val[maxv],anc[maxv][20],ans=0,dis[maxv],g[maxv],nume=0; void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void dfs1(int x) { for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=anc[x][0]) { anc[v][0]=x;dis[v]=dis[x]+1; dfs1(v); } } } void get_table() { for (int e=1;e<=19;e++) for (int i=1;i<=n;i++) anc[i][e]=anc[anc[i][e-1]][e-1]; } int lca(int x,int y) { if (dis[x]<dis[y]) swap(x,y); for (int e=19;e>=0;e--) { if ((dis[anc[x][e]]>=dis[y]) && (anc[x][e])) x=anc[x][e]; } if (x==y) return x; for (int e=19;e>=0;e--) { if (anc[x][e]!=anc[y][e]) { x=anc[x][e]; y=anc[y][e]; } } return anc[x][0]; } void dfs2(int x) { for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=anc[x][0]) { dfs2(v); val[x]+=val[v]; } } ans=max(ans,val[x]); } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } dfs1(1);get_table(); for (int i=1;i<=k;i++) { scanf("%d%d",&x,&y); int t=lca(x,y); val[x]++;val[y]++;val[t]--;val[anc[t][0]]--; } dfs2(1); printf("%d\n",ans); return 0; }
BZOJ 4390 Max Flow
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。