【洛谷P2680】运输计划
2024-08-25 20:33:59
题目链接
题目大意：
一棵\(n\)个点的带边权的数，给定\(m\)条树上两点间的路径，现在你可以让树上任意一条边的权值变为零，
问如何选边使得\(m\)条路径中边权和最大的路径的边权和最小
\(\mathcal{solution}\)
这是\(NOIP2015\)的\(Day2T3\)，感觉难度是比较大的
我首先想到的是，要选的边一定在边权和最大的路径上
于是我们可以先用\(lca\)找出边权和最大的路径的起始点，复杂度\(O(mlogn)\)
然后一遍\(dfs\)找出这个路径上所有的边，复杂度\(O(n)\)
之后枚举这个路径上的边，将它置为零，再重新\(dfs\)更新\(f\)数组，
然后枚举每条路径，求每条路径的权值和
复杂度\(O(n(n+mlogn))\)，只有\(40\)分
对于\(m=1\)的情况，我们可以直接一遍\(dfsO(n)\)解决
这样就有\(50\)分了
\(50\)分代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 300010
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
int x=0; char c=getchar();
while(c<'0')c=getchar();
while(c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
int n,m,Head[N],num=1;
struct NODE{
int to,w,next;
} e[N<<1];
inline void add(int x,int y,int w){
e[++num].to=y;
e[num].w=w;
e[num].next=Head[x];
Head[x]=num;
}
struct Data{ //路径的起始点
int x,y;
} a[N];
int f[N][25],sum[N][25],dep[N];
void dfs(int now,int fa){
f[now][0]=fa;
dep[now]=dep[fa]+1;
for(int i=1;(1<<i)<=dep[now];++i){
f[now][i]=f[f[now][i-1]][i-1];
sum[now][i]=sum[now][i-1]+sum[f[now][i-1]][i-1];
}
for(int i=Head[now];i;i=e[i].next)
if(e[i].to!=fa){
sum[e[i].to][0]=e[i].w;
dfs(e[i].to,now);
}
}
inline int Get_Sum(int x,int y){ //lca求边权和
int Sum=0;
if(dep[x]!=dep[y]){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0&&dep[x]>dep[y];--i)
if(dep[f[x][i]]>=dep[y])
Sum+=sum[x][i],x=f[x][i];
}
if(x==y) return Sum;
for(int i=20;i>=0;--i)
if(f[x][i]!=f[y][i]){
Sum+=sum[x][i]+sum[y][i];
x=f[x][i],y=f[y][i];
}
return Sum+sum[x][0]+sum[y][0];
}
int path[N],cnt;
bool dfs1(int now,int fa,int gl){ //已知起、始点，找出整条路径
if(now==gl) return 1;
for(int i=Head[now];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
path[++cnt]=i;
if(dfs1(v,now,gl)) return 1;
--cnt;
}
return 0;
}
int main()
{
n=read(),m=read();
int x,y,w;
for(int i=1;i<n;++i){
x=read(),y=read(),w=read();
add(x,y,w),add(y,x,w);
}
for(int i=1;i<=m;++i)
a[i].x=read(),a[i].y=read();
if(m==1){
dfs1(a[1].x,0,a[1].y);
int max2=0,sum2=0;
for(int i=1;i<=cnt;++i)
sum2+=e[path[i]].w,max2=max(max2,e[path[i]].w);
printf("%d\n",sum2-max2);
return 0;
}
dfs(1,0);
int k=0,maxx=0;
for(int i=1;i<=m;++i){
int t=Get_Sum(a[i].x,a[i].y);
if(t>maxx) maxx=t,k=i;
}
int minn=INF;
dfs1(a[k].x,0,a[k].y);
for(int i=1;i<=cnt;++i){
int k=path[i];
int temp=e[k].w;
e[k].w=e[k^1].w=0;
dfs(1,0);
e[k].w=e[k^1].w=temp;
int maxx=0;
for(int j=1;j<=m;++j)
maxx=max(maxx,Get_Sum(a[j].x,a[j].y));
minn=min(minn,maxx);
}
printf("%d\n",minn);
return 0;
}
我们考虑如何搞到\(100\)分
我们回到刚才的“题目大意”上来
问如何选边使得\(m\)条路径中\(\color{red}{边权和最大的路径的边权和最小}\)
这就提示我们要二分答案了
我们考虑二分一个答案\(mid\)表示最小的最大路径边权和
如何判断呢？
我们可以发现，最终被我们置为零的边 一定被 所有的一开始边权和大于\(mid\)的路径 覆盖了一遍
而当满足上面条件时，边权和最大的路径减去这条边的长度\(\leq mid\),那么这个\(mid\)就是可以满足的
我们可以用树上差分来求哪条边被所有一开始不满足条件的路径覆盖了，如果不存在这样的边，说明不存在方案满足当前\(mid\)
总的复杂度是\(O(mlogn+(m+n)logSum_{max})\)
然而最后一个点（\(luogu\)的\(\#13\)）十分毒瘤，需要各种卡常(好歹没爆栈(雾
\(100\)分代码:
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define N 300010
#define root (20181111%n+1)
#define re
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
//#define swap(a,b) (a^=b^=a^=b)
inline int Max(int a, int b){
int diff=b-a;return b-(diff&(diff>>31));
}
const int INF=0x3f3f3f3f,ch_top=4e7+3;
char ch[ch_top],*now_r=ch-1;
inline int read(){
while(*++now_r<'0');
re int x=*now_r-'0';
while(*++now_r>='0') x=(x<<3)+(x<<1)+*now_r-'0';
return x;
}
int n,m,Head[N],num=1,mid,ha;
struct NODE{
int to,w,next;
} e[N<<1];
struct Data{
int x,y,sum,lca;
} a[N];
int f[N][25],sum[N][25],dep[N],Max_sum;
inline void dfs(int now,int fa){
f[now][0]=fa; dep[now]=dep[fa]+1;
for(re int i=1;(1<<i)<=dep[now];++i){
f[now][i]=f[f[now][i-1]][i-1];
sum[now][i]=sum[now][i-1]+sum[f[now][i-1]][i-1];
}
for(re int i=Head[now],v=e[i].to;i;i=e[i].next,v=e[i].to)
if(v!=fa)sum[v][0]=e[i].w,dfs(v,now);
}
inline void Get_Lca(int p){
int Sum=0,x=a[p].x,y=a[p].y;
if(dep[x]!=dep[y]){
if(dep[x]<dep[y]) x^=y^=x^=y;
for(re int i=19;dep[x]>dep[y];--i)
if(dep[f[x][i]]>=dep[y]){
Sum+=sum[x][i];
x=f[x][i];
}
}
if(x==y){a[p].sum=Sum;a[p].lca=x;return;}
for(re int i=19;i>=0;--i)
if(f[x][i]!=f[y][i]){
Sum+=sum[x][i]+sum[y][i];
x=f[x][i]; y=f[y][i];
}
a[p].sum=Sum+sum[x][0]+sum[y][0];
a[p].lca=f[x][0];
}
int diff[N];
bool dfs1(int now,int len,int fa){
int tot=diff[now];
for(re int i=Head[now],v=e[i].to;i;i=e[i].next,v=e[i].to)
if(v!=fa){
if(dfs1(v,e[i].w,now)) return 1;
tot+=diff[v];
}
diff[now]=tot;
if(tot==ha&&Max_sum-len<=mid)
return 1;
return 0;
}
inline bool check(){
ha=0;
memset(diff,0,sizeof(diff));
for(re int i=1;i<=m;++i)
if(a[i].sum>mid){
++ha;
++diff[a[i].x],++diff[a[i].y];
diff[a[i].lca]-=2;
}
return dfs1(root,0,0);
}
int main()
{
// freopen("a.in","r",stdin);
// int size = 256 << 20; //250M
// char*p=(char*)malloc(size) + size;
// __asm__("movl %0, %%esp\n" :: "r"(p) );
fread(ch,1,ch_top,stdin);
n=read(),m=read();
int x,y,w;
for(re int i=1;i<n;++i){
x=read(),y=read(),w=read();
e[++num].to=y;
e[num].w=w;
e[num].next=Head[x];
Head[x]=num;
e[++num].to=x;
e[num].w=w;
e[num].next=Head[y];
Head[y]=num;
}
dfs(root,0);
for(re int i=1;i<=m;++i){
a[i].x=read(),a[i].y=read();
Get_Lca(i);
Max_sum=Max(Max_sum,a[i].sum);
}
re int l(0),r=Max_sum;
while(l<r){
mid=(l+r)>>1;
if(check()) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
最新文章
- Android 手机卫士--导航界面1的布局编写
- Android ExpandableGridView的实现
- hadoop2.6.4 搭建伪分布式
- Salesforce注册开发者账号
- 查看nginx配置文件路径
- Alpha阶段第五次Scrum Meeting
- iomanip,setw(),setw: undeclared identifier
- c#高级语言编程（第一部分）
- live555—VS2010/VS2013 下live555编译、使用及测试(转载)
- JVM 堆和栈的区别
- Weave 网络结构分析 - 每天5分钟玩转 Docker 容器技术（64）
- 从JS的深拷贝与浅拷贝到jq的$.extend()方法
- 关于netcore 发布到服务器的准备
- 通过sftp操作Linux服务器上的文件(java)
- 分布式系统登录功能拦截器的实现以及cookie的共享问题（利用cookie实现session在分布式系统的共享）
- restful framework之权限组件
- spring事务的隔离级别（透彻理解）
- HDUOJ-----1066Last non-zero Digit in N!
- GPU的历史：从固定管线到可编程管线再到通用计算平台
- github注册与使用