2018 ACM-ICPC World Finals 部分题题解

题面

Problem C. Conquer the World

题目大意:给定一棵树,树有边权。每个点上有\(a_i\)个士兵,且每个点最终需要\(b_i\)个士兵。
求最小代价。
\(n\) \(\leq\) \(2.5*10^5\),\(a_i\),\(b_i\) \(\leq\) \(1e9\)。
题解:显然,我们可以直接用这棵树跑费用流。但\(n\)太大了。所以我们只能模拟一下费用流的过程了。
首先,为了保证所有的\(b_i\)都能选满,我们先给每个\(b_i\)加一个-INF的权值。
考虑维护两个堆,分别记录\(a\)的信息和\(b\)的信息。
DFS这棵树,设当前节点为\(u\)。将\(u\)的所有儿子的堆全部合并,每个点的初始权值是\(dis_i\)和\(dis_i\)-INF,
指的是\(i\)到1号节点的距离。这个可以用左偏树或者stl里的pb_ds实现。
将子树信息上传完成后,开始尝试将它们两两配对。
配对终止的条件是两个堆顶元素匹配的权值\(\geq\) 0。
然后考虑如何像费用流那样进行反悔操作。
如果当前的一个匹配点和另外一个点匹配了,那么就要撤销之前的匹配。列出两次匹配的关系式,我们就可以分别得出计算\(a\),\(b\)反悔代价的算式。
因为一个点的\(a\)和\(b\)不会同时反悔,且\(\sum b_i\)也不大,所以做法是正确的。
具体的反悔实现可以看我的代码。
时间复杂度:O(\(nlogn\))
代码:

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class D>I read(D &res){
	res=0;register D g=1;register char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')g=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch^48);
		ch=getchar();
	}
	res*=g;
}
const ll INF=1e12+7;
struct E{
	int to,nt,w;
}e[505000];
#define T e[k].to
queue<int>q;
struct Dat{
	ll w,f;
	Dat(ll _w=0,ll _f=0){w=_w;f=_f;}
	friend bool operator < (Dat x,Dat y){return x.w>y.w;}
}d[2000000];
int now,cnt,ch[2000000][2],dis[2000000],root[303000],rt[303000];
int n,m,X,Y,W,a[303000],b[303000],head[303000],tot,sum;
ll dep[303000],ans;
IN new_node(){
	re res;
	if(q.empty())return ++cnt;
	res=q.front();q.pop();
	ch[res][0]=ch[res][1]=dis[res]=d[res].w=d[res].f=0;
	return res;
}
I add(int x,int y,int w){e[++tot].to=y;e[tot].nt=head[x];head[x]=tot;e[tot].w=w;}
IN merge(int x,int y){
	if(!x||!y)return x+y;
	if(d[x]<d[y])swap(x,y);
	ch[x][1]=merge(ch[x][1],y);
	if(dis[ch[x][0]]<dis[ch[x][1]])swap(ch[x][0],ch[x][1]);
	dis[x]=dis[ch[x][1]]+1;
	return x;
}
I D_1(int x,int fa,ll depth){
	dep[x]=depth;
	if(a[x])d[x]=Dat(dep[x],a[x]),root[x]=x,dis[x]=0;else root[x]=0;
	if(b[x])d[x+n]=Dat(dep[x]-INF,b[x]),rt[x]=x+n,dis[x+n]=0;else rt[x]=0;
	for(re k=head[x];k!=-1;k=e[k].nt){
		if(T==fa)continue;
		D_1(T,x,depth+e[k].w);
		root[x]=merge(root[x],root[T]);
		rt[x]=merge(rt[x],rt[T]);
	}
	while(root[x]&&rt[x]&&d[root[x]].w+d[rt[x]].w-2*dep[x]<0){
		ll vala=d[root[x]].w,valb=d[rt[x]].w,tmp=min(d[root[x]].f,d[rt[x]].f),nowa=d[root[x]].f-tmp,nowb=d[rt[x]].f-tmp;
		ans+=(vala+valb-2*dep[x])*tmp;
		q.emplace(root[x]);q.emplace(rt[x]);
		//cout<<"!"<<root[x]<<" "<<rt[x]<<" "<<tmp<<" "<<vala<<" "<<valb<<" "<<dep[x]<<" "<<nowa<<" "<<nowb<<endl;
		root[x]=merge(ch[root[x]][0],ch[root[x]][1]);
		rt[x]=merge(ch[rt[x]][0],ch[rt[x]][1]);
		if(tmp){
		now=new_node();d[now]=Dat(2*dep[x]-valb,tmp);dis[now]=0;root[x]=merge(root[x],now);
		now=new_node();d[now]=Dat(2*dep[x]-vala,tmp);dis[now]=0;rt[x]=merge(rt[x],now);
		}
		if(nowa)now=new_node(),d[now]=Dat(vala,nowa),dis[now]=0,root[x]=merge(root[x],now);
		if(nowb)now=new_node(),d[now]=Dat(valb,nowb),dis[now]=0,rt[x]=merge(rt[x],now);
	}
}
int main(){
	read(n);C(head,-1);tot=-1;cnt=n<<1;dis[0]=-1;
	F(i,1,n-1){
		read(X);read(Y);read(W);
		add(X,Y,W);add(Y,X,W);
	}
	F(i,1,n){
		read(a[i]),read(b[i]);
		re tmp=min(a[i],b[i]);a[i]-=tmp;b[i]-=tmp;
		sum+=b[i];
	}
	D_1(1,0,0);
	/*while(rt[1]){
		ll vala=d[root[1]].w,valb=d[rt[1]].w,tmp=min(d[root[1]].f,d[rt[1]].f),nowa=d[root[1]].f-tmp,nowb=d[rt[1]].f-tmp;
		ans+=(vala+valb-2*dep[1])*tmp;//cout<<"!"<<tmp<<endl;
		root[1]=merge(ch[root[1]][0],ch[root[1]][1]);
		rt[1]=merge(ch[rt[1]][0],ch[rt[1]][1]);
		if(nowa)++now,d[now]=Dat(vala,nowa),dis[now]=0,root[1]=merge(root[1],now);
		if(nowb)++now,d[now]=Dat(valb,nowb),dis[now]=0,rt[1]=merge(rt[1],now);
		//cout<<now<<endl;
	}*/
	printf("%lld",ans+(ll)INF*sum);
	return 0;
}
/*
3
1 2 5
3 1 5
2 1
5 0
1 3
6
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
0 0
1 0
2 1
2 1
0 1
0 1
*/
上一篇:小米icpc邀请赛第一场 E


下一篇:【思维】构造——ICPC NEAU B