BZOJ #1999 [Noip2007]Core 树网的核
Description
设 $T=(V, E, W)$ 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称 $T$ 为树网（treenetwork），其中 $V, E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。 路径：树网中任何两结点 $a,b$ 都存在唯一的一条简单路径，用 $d(a,b)$ 表示以 a,b 为端点的路径的长度，它是该路径上各边长度之和。我们称 $d(a,b)$ 为 $a,b$ 两结点间的距离。 一点 $v$ 到一条路径 $P$ 的距离为该点与 $P$ 上的最近的结点的距离：$d(v，P)=min\{d(v，u)，u 为路径 P 上的结点\}$。 树网的直径：树网中最长的路径称为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距 $ECC(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离，即 。 任务：对于给定的树网 $T=(V, E,W)$ 和非负整数 $s$，求一个路径 $F$，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$（可以等于 $s$），使偏心距 $ECC(F)$ 最小。我们称这个路径为树网 $T=(V,E,W)$ 的核（Core）。必要时，$F$ 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中，$A-B$ 与 $A-C$ 是两条直径，长度均为 $20$。点 W 是树网的中心，$EF$ 边的长度为 $5$。如果指定 $s=11$，则树网的核为路径 $DEFG$（也可以取为路径 $DEF$），偏心距为 $8$。如果指定 $s=0$（或 $s=1$、$s=2$），则树网的核为结点 $F$，偏心距为 $12$。
Solution
找到一条直径，预处理好每个点的偏心距，从直径中点贪心扩散，选择长的那条边扩展直到核长度达到 $s$ 为止，最后还要更新到两端的距离。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int n,S,pre[500005],d[500005],dd[500005],bfsmax=0,bfsres,dfsmax=0,t[500005],m,p[500005];
bool v[500005];
int last[1000005],to[1000005],nextt[1000005],s[1000005],top=0;
void add(int a,int b,int c){
nextt[++top]=last[a];
to[top]=b;
s[top]=c;
last[a]=top;
}
void bfs(int from){
memset(pre,0,sizeof(pre));
memset(d,0,sizeof(d));
memset(v,0,sizeof(v));
bfsmax=0;
queue<int> q;
q.push(from);
d[from]=0;
v[from]=1;
while (!q.empty()){
int x=q.front();
q.pop();
for (int i=last[x];i;i=nextt[i]){
int y=to[i];
if (v[y]){
continue;
}
v[y]=1;
d[y]=d[x]+s[i];
pre[y]=x;
q.push(y);
}
if (d[x]>bfsmax){
bfsmax=d[x];
bfsres=x;
}
}
}
void dfs(int x){
v[x]=1;
dfsmax=max(dfsmax,d[x]);
for (int i=last[x];i;i=nextt[i]){
int y=to[i];
if (v[y]){
continue;
}
d[y]=d[x]+s[i];
dfs(y);
}
}
int main(){
n=read();S=read();
for (int i=1;i<=n-1;i++){
int a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,c);
}
bfs(1);
int a=bfsres;
bfs(a);
int b=bfsres;
memset(d,0,sizeof(d));
memset(v,0,sizeof(v));
for (int i=b;i;i=pre[i]){
v[i]=1;
}
for (int i=b;i;i=pre[i]){
dfsmax=0;
dfs(i);
t[i]=dfsmax;
p[++m]=i;
dd[m]=d[i];
}
reverse(p+1,p+1+m);
bfs(a);
for (int i=1;i<=m;i++){
dd[i]=d[p[i]];
}
int l,r;
for (int i=1;i<=m;i++){
if (d[p[i]]>=d[b]/2){
l=r=i;
break;
}
}
while (1){
if (dd[r]-dd[l]+min(dd[r+1]-dd[r],dd[l]-dd[l-1])>S||(l==1&&r==m)){
break;
}
if (dd[l]-dd[l-1]>dd[r]-dd[r+1]){
if (l>1&&dd[r]-dd[l-1]<=S){
l--;
}else{
r++;
}
}else{
if (r<m&&dd[r+1]-dd[l]<=S){
r++;
}else{
l--;
}
}
}
int maxx=0;
for (int i=l;i<=r;i++){
maxx=max(maxx,t[p[i]]);
}
maxx=max(maxx,max(dd[m]-dd[r],dd[l]-dd[1]));
cout<<maxx;
}
#2936 [Poi1999]降 水
Description
有这样一块土地，它可以被划分成 $N×M$ 个正方形小块，每块面积是一平方英寸，第 $i$ 行第 $j$ 列的小块可以表示成 $P(i,j)$。这块土地高低不平，每一小块地 $P(i,j)$ 都有自己的高度 $H(i,j)$（单位是英寸）。
一场倾盆大雨后，这块地由于地势高低不同，许多低洼地方都积存了不少降水。假如你已经知道这块土地的详细信息，你能求出它最多能积存多少立方英寸的降水么？
Solution
从边缘开始 BFS，每次选择相邻最低的一块，更新高度并扩展
Code
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,h;
bool operator < (const node &a) const {
return h>a.h;
}
};
priority_queue<node> q;
int n,m,s[105][105],t[105][105],v[105][105],d[4][2]={{1,0},{-1,0},{0,1},{0,-1}},ans=0;
int main(){
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>s[i][j];
t[i][j]=s[i][j];
if (i==1||i==n||j==1||j==m){
q.push((node){i,j,s[i][j]});
v[i][j]=1;
}
}
}
while (!q.empty()){
node now=q.top();
q.pop();
for (int i=0;i<=3;i++){
int x=now.x+d[i][0];
int y=now.y+d[i][1];
if (v[x][y]){
continue;
}
if (x<=1||x>=n||y<=1||y>=m){
continue;
}
s[x][y]=max(s[x][y],now.h);
v[x][y]=1;
q.push((node){x,y,s[x][y]});
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
ans+=s[i][j]-t[i][j];
}
}
cout<<ans;
}
#1907 树的路径覆盖
Description
Solution
贪心
Code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int T,n,m,last[200005],to[200005],nextt[200005],v[200005],size[200005],top=0,ans=0;
void add(int a,int b){
nextt[++top]=last[a];
to[top]=b;
last[a]=top;
}
void dfs(int x,int fa){
size[x]=1;
int sons=0;
for (int i=last[x];i;i=nextt[i]){
if (to[i]==fa){
continue;
}
dfs(to[i],x);
size[x]+=size[to[i]];
if (!v[to[i]]){
sons++;
}
}
if (sons==1){
size[x]--;
}
if (sons>=2){
size[x]-=2;
v[x]=1;
}
}
int main(){
T=read();
while (T--){
memset(last,0,sizeof(last));
memset(to,0,sizeof(to));
memset(nextt,0,sizeof(nextt));
memset(v,0,sizeof(v));
memset(size,0,sizeof(size));
top=0;
n=read();
for (int i=1;i<=n-1;i++){
int a=read(),b=read();
add(a,b);
add(b,a);
}
dfs(1,0);
cout<<size[1]<<endl;
}
}
#1270 [BeijingWc2008]雷涛的小猫
Description
雷涛的小猫雷涛同学非常的有爱心，在他的宿舍里，养着一只因为受伤被救助的小猫（当然，这样的行为是违反学生宿舍管理条例的）。 在他的照顾下，小猫很快恢复了健康，并且愈发的活泼可爱了。可是有一天，雷涛下课回到寝室，却发现小猫不见了！经过一番寻找，才发现她正趴在阳台上对窗外的柿子树发呆…在北京大学的校园里，有许多柿子树，在雷涛所在的宿舍楼前，就有 $N$ 棵。并且这 $N$ 棵柿子树每棵的高度都是 $H$。冬天的寒冷渐渐笼罩了大地，树上的叶子渐渐掉光了，只剩下一个个黄澄澄的柿子，看着非常喜人。而雷涛的小猫恰好非常的爱吃柿子，看着窗外树上的柿子，她十分眼馋，于是决定利用自己敏捷的跳跃能力跳到树上去吃柿子。小猫可以从宿舍的阳台上跳到窗外任意一棵柿子树的树顶。之后，她每次都可以在当前位置沿着当前所在的柿子树向下跳 $1$ 单位距离。当然，小猫的能力远不止如此，她还可以在树之间跳跃。每次她都可以从当前这棵树跳到另外的任意一棵，在这个过程中，她的高度会下降 $Delta$ 单位距离。每个时刻，只要她所在的位置有柿子，她就可以吃掉。整个“吃柿子行动”一直到小猫落到地面上为止。雷涛调查了所有柿子树上柿子的生长情况。饱很想知道，小猫从阳台出发，最多能吃到多少柿子？他知道写一个程序可以很容易的解决这个问题，但是他现在懒于写任何代码。于是，现在你的任务就是帮助雷涛写一个这样的程序。左图是 $N=3$，$H=10$，$Delta=2$ 的一个例子。小猫按照图示路线进行跳跃，可以吃到最多的 $8$ 个柿子。
Solution
水 DP，$f[x]$ 表示 $x$ 高度最大值，$g[x]$ 表示当前高度 $x$ 树最大值。
#include<bits/stdc++.h>
using namespace std;
int n,h,d,s[2005][2005],f[2005],g[2005];
int main(){
cin>>n>>h>>d;
for (int i=1;i<=n;i++){
int m,x;
cin>>m;
while (m--){
cin>>x;
s[i][x]++;
}
}
g[h+1]=0;
for (int i=h;i>=1;i--){
for (int j=1;j<=n;j++){
g[j]=max(g[j],f[min(i+d,h+1)])+s[j][i];
f[i]=max(f[i],g[j]);
}
}
cout<<f[1];
}
|´・ω・)ノ
这个代码的插件是哪个qwq
嗯哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
把别人评论区变臭的屑，自裁，请
真的厉害enmm…