刷题日记 2021__1
题目描述
有一个树形的水系,由 N-1 条河道和 N 个交叉点组成。
我们可以把交叉点看作树中的节点,编号为 1~N,河道则看作树中的无向边。
每条河道都有一个容量,连接 x 与 y 的河道的容量记为 c(x,y)。
河道中单位时间流过的水量不能超过河道的容量。
有一个节点是整个水系的发源地,可以源源不断地流出水,我们称之为源点。
除了源点之外,树中所有度数为 1 的节点都是入海口,可以吸收无限多的水,我们称之为汇点。
也就是说,水系中的水从源点出发,沿着每条河道,最终流向各个汇点。
在整个水系稳定时,每条河道中的水都以单位时间固定的水量流向固定的方向。
除源点和汇点之外,其余各点不贮存水,也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
整个水系的流量就定义为源点单位时间发出的水量。
在流量不超过河道容量的前提下,求哪个点作为源点时,整个水系的流量最大,输出这个最大值。
AC Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rg register
using namespace std;
inline int sread()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return f*x;
}
const int maxn=200050;
inline int minx(int a,int b)
{
return a<b?a:b;
}
inline int maxx(int a,int b)
{
return a>b?a:b;
}
int h[maxn],cnt;
struct node{
int next;
int to;
int val;
}edg[2*maxn];
void add(int u,int v,int val)
{
++cnt;
edg[cnt].next=h[u];
edg[cnt].to=v;
edg[cnt].val=val;
h[u]=cnt;
}
int degree[maxn];
int T,n;
int d[maxn];
int dfs1(int u,int fa)
{
int p=0;d[u]=0;
for(rg int i=h[u];i;i=edg[i].next)
{
int v=edg[i].to;
if(v==fa) continue;
p+=minx(dfs1(v,u),edg[i].val);
}
if(degree[u]!=1) return d[u]=p;
else return edg[h[u]].val;
}
int f[maxn];
int ans,p;
void dfs2(int u,int fa)
{
for(int i=h[u];i;i=edg[i].next)
{
int v=edg[i].to;
if(v==fa) continue;
if(degree[u]==1) f[v]=d[v]+edg[i].val;
else f[v]=d[v]+minx(f[u]-minx(d[v],edg[i].val),edg[i].val);
ans=maxx(ans,f[v]);
dfs2(v,u);
}
}
int main()
{
T=sread();
int x,y,z;
for(rg int qqq=1;qqq<=T;++qqq)
{
n=x=y=z=ans=cnt=p=0;
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(degree,0,sizeof(degree));
memset(h,0,sizeof(h));
n=sread();
for(rg int i=1;i<n;++i)
{
x=sread();y=sread();z=sread();
add(x,y,z);add(y,x,z);
degree[x]++;
degree[y]++;
}
f[1]=dfs1(1,-1);
dfs2(1,-1);
printf("%d\n",maxx(f[1],ans));
}
return 0;
}