[luogu]P3629 [APIO2010]巡逻
标签：sed \n set none printf == col 结合 span
原题链接：P3629 [APIO2010]巡逻
题意
给定一棵树，每次要走过每条边。
现在要求加$k$条边，使得走过每条边后走过的距离最小，求这个最小值。
分析
首先不考虑加边，也就是说$k=0$时，是一棵树，显然每条边要经过两次。
考虑加一条边，很容易发现形成的环上的点只需要经过一遍，最终经过的距离就是$((n-1)\times 2-len+2)$，$len$是最大环的长度，明显是树的直径$+1$。
考虑加两条边对答案有什么影响。
分两类考虑：
1.第一次形成的环和第二次没重叠：答案继续减去$len_2+2$.
2.第一次形成的环和第二次有重叠：画过图就很容易发现，重叠部分是经过了两次的，答案就是$((n-1)\times 2-len_1+2_len_2+2+k)$,$k$是这个重叠部分的长度。
那么我们就考虑怎么求出这个重叠部分了。
考虑差分。
第一次已经减去了这个长度，第二次减去这个长度的相反数就相当于加回上了这个长度。
那么我们只需要把直径上的边权置为$-1$，再求一次树的直径即可。
注意第二次的直径可以为$0$（自环）。
实现的方式
我们常用dfs写树的直径，但是我们发现这样子是不能跑负权图的，因为dfs不能统计负权的情况。
而树形dp求树的直径虽然可以跑负权图，但是却很难转移出其他量。
我们结合这两种算法，在第一次时用dfs求出直径，并保存出直径上的边，第二次再跑一次树形dp就可以了。
保存直径上的边的时候，我们需要一点小技巧。
运用费用流中求增广路的方法，我们保存每个节点的祖先节点（从哪里转移过来），并利用成对储存的方法保存每条边和它的反向边。
具体实现见代码。
代码
#include using namespace std;
const int N=1e5+1000;
int read(){
char c;int num,f=1;
while(c=getchar(),!isdigit(c))if(c==‘-‘)f=-1;num=c-‘0‘;
while(c=getchar(), isdigit(c))num=num*10+c-‘0‘;
return f*num;
}
int n,k,ans,pre[N*2],maxn,id,dis[N*2];
int head[N],nxt[N*2],ver[N*2],edge[N*2],tot=1;
void add_edge(int u,int v,int w){
ver[++tot]=v;edge[tot]=w;nxt[tot]=head[u];head[u]=tot;
ver[++tot]=u;edge[tot]=w;nxt[tot]=head[v];head[v]=tot;
}
void dfs(int x,int val,int pr){
if(val>maxn){
maxn=val;
id=x;
}
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==pr)continue;
pre[ver[i]]=i;
dfs(ver[i],val+edge[i],x);
}
}
int dfs_get_diam(){
dfs(1,0,1);
memset(pre,0,sizeof(pre));
maxn=0;
dfs(id,0,id);
return maxn;
}
void dp_get_diam(int x,int fa){
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==fa)continue;
dp_get_diam(ver[i],x);
maxn=max(maxn,dis[x]+dis[ver[i]]+edge[i]);
dis[x]=max(dis[x],dis[ver[i]]+edge[i]);
}
}
int main()
{
n=read();k=read();
for(int i=1;i){
int u,v;
u=read();v=read();
add_edge(u,v,1);
ans+=2;
}
ans-=dfs_get_diam()-1;
if(k==1){
printf("%d\n",ans);
return 0;
}
for(int i=pre[id];i;i=pre[ver[i^1]]){
edge[i]=-1;
edge[i^1]=-1;
}
maxn=0;
dp_get_diam(1,1);
ans-=maxn-1;
printf("%d\n",ans);
return 0;
}
View Code
[luogu]P3629 [APIO2010]巡逻
标签：sed \n set none printf == col 结合 span
原文地址：https://www.cnblogs.com/onglublog/p/10030017.html
评论