首页 > 代码库 > bzoj4390[Usaco2015 dec]Max Flow*
bzoj4390[Usaco2015 dec]Max Flow*
bzoj4390[Usaco2015 dec]Max Flow
题意:
给定一棵有N个点的树,所有节点的权值都为0。有K次操作,每次指定两个点s,t,将s到t路径上所有点的权值都加一。请输出K次操作完毕后权值最大的那个点的权值。n≤50000,k≤100000。
题解:
先链剖把树变为链。然后用数组区间加的方式(即在数组区间左端点位置增加值,数组区间右端点+1位置增加这个值的相反数,最后扫一遍a[i]+=a[i-1])累计权值。类似bzoj3631
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 50010 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0;10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12 return f*x;13 }14 int sm[maxn],sz[maxn],dep[maxn],fa[maxn],top[maxn],pos[maxn],n,q,ans,tot;15 struct e{int t,n;}es[maxn*2]; int g[maxn],ess;16 void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}17 void dfs1(int x,int f){18 sz[x]=1;19 for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){20 fa[es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs1(es[i].t,x); sz[x]+=sz[es[i].t];21 }22 }23 void dfs2(int x,int f,int tp){24 pos[x]=++tot; top[x]=tp; int mx1=0,mx2=0;25 for(int i=g[x];i;i=es[i].n)if(es[i].t!=f&&sz[es[i].t]>mx1)mx1=sz[es[i].t],mx2=es[i].t;26 if(!mx2)return; dfs2(mx2,x,tp);27 for(int i=g[x];i;i=es[i].n)if(es[i].t!=f&&es[i].t!=mx2)dfs2(es[i].t,x,es[i].t);28 }29 void solve(int x,int y){30 for(;top[x]!=top[y];sm[pos[top[x]]]++,sm[pos[x]+1]--,x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);31 if(dep[x]>dep[y])swap(x,y); sm[pos[x]]++; sm[pos[y]+1]--;32 }33 int main(){34 n=read(); q=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y);} dfs1(1,0); dfs2(1,0,1);35 inc(i,1,q){int x=read(),y=read(); solve(x,y);}36 inc(i,1,n)sm[i]+=sm[i-1],ans=max(ans,sm[i]); printf("%d",ans); return 0;37 }
20160908
bzoj4390[Usaco2015 dec]Max Flow*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。