【寒假作业】【NOIP2015】运输计划

寒假作业是刷完05年到15年的NOIP题。。

当然本来是想的话可以做HNOI的看了看难度还是算了=-=

于是趁机来填NOIP2015的坑

这道题嘛。。就是首先二分答案。。

然后把长度大于这个答案的运输计划取个交集，找到这个交集里最大的边

然后用距离最长的运输计划-这条边，判断一下和二分出的答案的大小=-=

【听上去还是很容易的是吧？

然后关键就是怎么取交

这里可以用一下差分。。修改O(1) 之后全部扫一遍

【太神了

// <transport.cpp> - 02/07/16 12:23:52
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=300002;
int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],dis[MAXN],tf[MAXN],btf[MAXN];
int n,m,tot,maxl;
vector <pair<int,int> >b[MAXN];
struct PLAN{
	int a,b,v;
	bool operator <(PLAN b) const{return v<b.v;}
	bool operator >(PLAN b) const{return v>b.v;}
}plan[MAXN];
void dfs1(int x){
	siz[x]=1;son[x]=0;
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i].first;
		if(next==f[x])continue;
		dep[next]=dep[x]+1;
		tf[next]=b[x][i].second;
		dis[next]=dis[x]+tf[next];
		f[next]=x;
		dfs1(next);
		siz[x]+=siz[next];
		if(!son[x]||siz[son[x]]<siz[next])son[x]=next;
	}
}
void dfs2(int x,int y){
	w[x]=++tot;top[x]=y;btf[tot]=tf[x];
	if(son[x])dfs2(son[x],y);
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i].first;
		if(next==f[x]||next==son[x])continue;
		dfs2(b[x][i].first,b[x][i].first);
	}
}
int cd[MAXN];
void cf(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		cd[w[top[u]]]++;
		cd[w[u]+1]--;
		u=f[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	cd[w[v]+1]++;
	cd[w[u]+1]--;
}
bool check(int x){
	int i;
	for(i=1;i<=m;i++)if(plan[i].v>x)break;
	int sum=m-i+1;
	for(int o=1;o<=n;o++)cd[o]=0;
	for(;i<=m;i++)cf(plan[i].a,plan[i].b);
	int now=0,ans=0;
	for(int o=1;o<=n;o++){
		now+=cd[o];
		if(now==sum)ans=max(ans,btf[o]);
	}
	return maxl-ans<=x;
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=f[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	return v;
}
int main(){
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	n=getint(),m=getint();
	for(int i=1;i<=n-1;i++){
		int u=getint(),v=getint(),w=getint();
		b[u].push_back(make_pair(v,w));
		b[v].push_back(make_pair(u,w));
	}
	dfs1(1);dfs2(1,1);
	for(int i=1;i<=m;i++){
		plan[i].a=getint(),plan[i].b=getint();
		plan[i].v=dis[plan[i].a]+dis[plan[i].b]-(dis[lca(plan[i].a,plan[i].b)]<<1);
		maxl=max(maxl,plan[i].v);
	}
	sort(plan+1,plan+1+m);
	int l=0,r=maxl;
	while(l<r){
		int m=(l+r)>>1;
		if(check(m))r=m;
		else l=m+1;
	}
	cout<<l;
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

// <transport.cpp> - 02/07/16 12:23:52

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=300002;

int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],dis[MAXN],tf[MAXN],btf[MAXN];

int n,m,tot,maxl;

vector <pair<int,int> >b[MAXN];

struct PLAN{

int a,b,v;

bool operator <(PLAN b) const{return v<b.v;}

bool operator >(PLAN b) const{return v>b.v;}

}plan[MAXN];

void dfs1(int x){

siz[x]=1;son[x]=0;

for(int i=0;i<b[x].size();i++){

int next=b[x][i].first;

if(next==f[x])continue;

dep[next]=dep[x]+1;

tf[next]=b[x][i].second;

dis[next]=dis[x]+tf[next];

f[next]=x;

dfs1(next);

siz[x]+=siz[next];

if(!son[x]||siz[son[x]]<siz[next])son[x]=next;

}

void dfs2(int x,int y){

w[x]=++tot;top[x]=y;btf[tot]=tf[x];

if(son[x])dfs2(son[x],y);

for(int i=0;i<b[x].size();i++){

int next=b[x][i].first;

if(next==f[x]||next==son[x])continue;

dfs2(b[x][i].first,b[x][i].first);

}

int cd[MAXN];

void cf(int u,int v){

while(top[u]!=top[v]){

if(dep[top[u]]<dep[top[v]])swap(u,v);

cd[w[top[u]]]++;

cd[w[u]+1]--;

u=f[top[u]];

}

if(dep[u]<dep[v])swap(u,v);

cd[w[v]+1]++;

cd[w[u]+1]--;

}

bool check(int x){

int i;

for(i=1;i<=m;i++)if(plan[i].v>x)break;

int sum=m-i+1;

for(int o=1;o<=n;o++)cd[o]=0;

for(;i<=m;i++)cf(plan[i].a,plan[i].b);

int now=0,ans=0;

for(int o=1;o<=n;o++){

now+=cd[o];

if(now==sum)ans=max(ans,btf[o]);

}

return maxl-ans<=x;

}

int lca(int u,int v){

while(top[u]!=top[v]){

if(dep[top[u]]<dep[top[v]])swap(u,v);

u=f[top[u]];

}

if(dep[u]<dep[v])swap(u,v);

return v;

}

int main(){

freopen("transport.in","r",stdin);

freopen("transport.out","w",stdout);

n=getint(),m=getint();

for(int i=1;i<=n-1;i++){

int u=getint(),v=getint(),w=getint();

b[u].push_back(make_pair(v,w));

b[v].push_back(make_pair(u,w));

}

dfs1(1);dfs2(1,1);

for(int i=1;i<=m;i++){

plan[i].a=getint(),plan[i].b=getint();

plan[i].v=dis[plan[i].a]+dis[plan[i].b]-(dis[lca(plan[i].a,plan[i].b)]<<1);

maxl=max(maxl,plan[i].v);

}

sort(plan+1,plan+1+m);

int l=0,r=maxl;

while(l<r){

int m=(l+r)>>1;

if(check(m))r=m;

else l=m+1;

}

cout<<l;

return 0;

}