[USACO15DEC]最大流Max Flow(树链剖分,线段树)
2024-09-03 05:38:29
FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道,隔间编号从1到N。所有隔间都被管道连通了。
FJ有K(1≤K≤100,000)条运输牛奶的路线,第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间的压力是多少。
思路:
比较基础的树剖题
对于每条线路
我们维护一个区间最大值的线段树
通过树剖实现每个加1的操作
最后读取总最大值就好
代码:
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define rii register int i
#define rij register int j
using namespace std;
int fa[],top[],size[],nid[];
int head[],n,k,bnt,cnt,sd[],wes[];
struct ljb{
int to,nxt;
}y[];
struct tree{
int maxn,lazy;
}x[];
inline int rd(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
}
inline void add(int from,int to)
{
bnt++;
y[bnt].to=to;
y[bnt].nxt=head[from];
head[from]=bnt;
}
inline void pushdown(int bh)
{
x[bh*].lazy+=x[bh].lazy;
x[bh*].maxn+=x[bh].lazy;
x[bh*+].lazy+=x[bh].lazy;
x[bh*+].maxn+=x[bh].lazy;
x[bh].lazy=;
}
void addjl(int l,int r,int nl,int nr,int bh)
{
if(l<nl)
{
l=nl;
}
if(r>nr)
{
r=nr;
}
if(l==nl&&r==nr)
{
x[bh].lazy++;
x[bh].maxn++;
return;
}
if(x[bh].lazy!=)
{
pushdown(bh);
}
int mid=(nl+nr)/;
if(l<=mid)
{
addjl(l,r,nl,mid,bh*);
}
if(r>mid)
{
addjl(l,r,mid+,nr,bh*+);
}
x[bh].maxn=max(x[bh*].maxn,x[bh*+].maxn);
}
void dfs1(int wz,int nfa,int nsd)
{
fa[wz]=nfa;
sd[wz]=nsd;
size[wz]=;
int maxn=;
for(rii=head[wz];i!=;i=y[i].nxt)
{
int to=y[i].to;
if(to!=nfa)
{
dfs1(to,wz,nsd+);
size[wz]+=size[to];
if(size[to]>maxn)
{
wes[wz]=to;
maxn=size[to];
}
}
}
}
void dfs2(int wz,int ntop)
{
cnt++;
nid[wz]=cnt;
top[wz]=ntop;
if(wes[wz]==)
{
return;
}
dfs2(wes[wz],ntop);
for(rii=head[wz];i!=;i=y[i].nxt)
{
int to=y[i].to;
if(wes[wz]!=to&&fa[wz]!=to)
{
dfs2(to,to);
}
}
}
void addlj(int from,int to)
{
while(top[from]!=top[to])
{
if(sd[top[from]]<sd[top[to]])
{
swap(from,to);
}
addjl(nid[top[from]],nid[from],,n,);
from=fa[top[from]];
}
if(sd[from]>sd[to])
{
swap(from,to);
}
addjl(nid[from],nid[to],,n,);
from=fa[top[from]];
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=rd(),k=rd();
for(rii=;i<n;i++)
{
int from,to;
from=rd(),to=rd();
add(from,to);
add(to,from);
}
dfs1(,,);
dfs2(,);
for(rii=;i<=k;i++)
{
int from,to;
from=rd(),to=rd();
addlj(from,to);
}
cout<<x[].maxn;
}
最新文章
- Asp.net MVC 之异常处理
- Install MongoDB driver for PHP on XAMPP for Mac OSX
- USACO section1.2 Miking cows
- safari的input问题
- C++ Primer 学习笔记_88_用于大型程序的工具 --异常处理[续1]
- struts2入门
- HDU 1671 Phone List (Trie)
- mysql+mybatis递归调用
- 大白话5分钟带你走进人工智能-第十五节L1和L2正则几何解释和Ridge,Lasso,Elastic Net回归
- Aooms_微服务基础开发平台实战_003_配置文件与简单的web环境搭建
- Mybatis-Plus 3.0代码生成器
- Redis管道
- 个人博客作业-Week7
- 源码研究:php变量
- C# winform(计算器)
- 启动tomcat 报错:Neither the JAVA_HOME nor the JRE_HOME environment variable is defined
- js-ES6学习笔记-Proxy(2)
- MVC 4 Razor Design Sample Demo Project
- 使用jdk压缩war包
- C# 调用C++ DLL 的类型转换(转载版)
热门文章
- 转载:Windows下三分钟搭建Shadowoscks服务器端
- 安装 GraphicsMagick
- iOS设计模式 - 原型
- 乘风破浪:LeetCode真题_001_TwoSum
- MapReduce Design Patterns(chapter 2 (part 2))(三)
- Eclipse+Maven 项目创建
- php给$_POST赋值会导致值为空
- codeforces 703E Mishka and Divisors
- 【SQL.基础构建-第四节(4/4)】
- python接口测试:自动保存cookies