luoguP5201 [USACO19JAN] Shortcut G

题目背景

USACO 19 年一月月赛金组第三题

luogu题目传送门

题目描述

每天晚上，Farmer John 都会敲响一个巨大的铃铛，召唤他的奶牛们前来牛棚享用晚餐。奶牛们都急切地想要前往牛棚，所以她们都会沿着最短的路径行走。
农场可以描述为 $N$ 块草地（$1\le N\le 10,000$），方便起见编号为 $1\dots N$，牛棚位于草地 $1$。草地之间由 $M$ 条双向的小路连接（$N-1\le M\le 50,000$）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。

草地 $i$ 中有 $c_i$ 头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地 $7$、$3$、$6$、$1$ 的路径会优先于经过 $7$、$5$、$1$ 的路径，如果它们所消耗的时间相同）。

Farmer John 担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地 $1$）连接到某块他选择的其他草地的、通过时间为 $T$（$1\le T\le 10,000$）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。

请帮助 Farmer John 求出通过添加一条近道能够达到的总移动时间减少量的最大值。

输入格式

输入的第一行包含 $N$、$M$ 和 $T$。以下 $N$ 行包含 $c_1\dots c_N$，均为 $0\dots 10,000$ 范围内的整数。以下 $M$ 行，每行由三个整数 $a$、$b$ 和 $t$ 描述了一条小路，这条小路连接了草地 $a$ 和 $b$，通过时间为 $t$。所有的通过时间在 $1\dots 25,000$ 范围内。

输出格式

输出 Farmer John 可以达到的总移动时间的最大减少量。

输入输出样例

输入

5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7

输出

40

思路

根据目测法，这道题明显是最短路径

思考如果我们在节点 u 建了一条道节点 1 的边，哪些点到 1 的距离减少了？减少了多少？

首先，由于奶牛只有新建的边在原来的最短路径上时，它才可能走这条边。所以所有最短路径经过这个点的奶牛走的距离都会减少(包括这个点上的奶牛)

其次，如果走这条路可以减少距离，那么所有走这条路的奶牛减少的距离都是 $di{s}_{u,1}-T$，因为经过这个点的所有奶牛都要经过 u 到 1 的路径

那我们就定义 2 个数组siz[u]，dlt[u]，分别表示经过 u 点的奶牛数与在 u 点建边可以减少的距离，那答案即为 $ma{x}_{kϵn}^{k}siz[k]\ast dlt[k]$

dlt数组很好处理，$dlt[i]=di{s}_{i,1}-T(iϵn)$

siz数组不太好处理，根据我们在树状dp时得到的思路，如果我们可以把最短路径转化为一棵树，那就很好办了

我们创建一个数组pre[u]，表示u是由pre[u]更新而来，那么我们先将原来的图删去了，再个每个边
(u,pre[u])建一个双向边，然后像树状dp一样求出siz[u]就行了

最后我们发现，如果我们每一个点都跑一次建边，那么极限时间复杂度为 $O(n^2)$，这个时间复杂度是会超的。那我们就再用一个映射来保存是否建了这条边，如果建了这条边，那么立即退出，这样时间复杂度为 $O(n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
const ll N=5e5+5;
ll n,m,T,c[N];
ll h[N],to[N],w[N],ne[N],pre[N],tot,dlt[N],siz[N];
void add(ll u,ll v,ll d){
	tot++;to[tot]=v;w[tot]=d;ne[tot]=h[u];h[u]=tot;
}
ll dis[N],vis[N];
map<pi,bool>mp;//保存是否建了这条边 
void chang(ll u){//重新建边 
	if(!pre[u])return;
	if(mp[{u,pre[u]}])return;
	else{
		add(pre[u],u,0);add(u,pre[u],0);
		mp[{pre[u],u}]=mp[{u,pre[u]}]=1;
		chang(pre[u]);
	}
}
void init(){//将图清空 
	memset(h,0,sizeof(h));
	memset(w,0,sizeof(w));
	memset(ne,0,sizeof(ne));
	memset(to,0,sizeof(to));
	tot=0;
}
void dfs(ll u,ll fa){//深搜求解siz数组 
	siz[u]+=c[u];
	for(ll i=h[u];i;i=ne[i]){
		ll v=to[i];
		if(v==fa)continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
void spfa(ll o){//spfa求 o 到所有点的距离  
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	vis[o]=1;dis[o]=0;queue<ll>q;q.push(o);
	while(!q.empty()){
		ll u=q.front();q.pop();vis[u]=0;
		for(ll i=h[u];i;i=ne[i]){
			ll v=to[i];
			if(dis[v]>dis[u]+w[i]||(dis[v]==dis[u]+w[i]&&u<pre[v])){
				dis[v]=dis[u]+w[i];
				pre[v]=u;
				if(!vis[v]){
					q.push(v);vis[v]=1;
				}
			}
		}
	}
	for(ll i=1;i<=n;i++)dlt[i]=(dis[i]-T);//求出dlt数组 
}
int main(){
	cin>>n>>m>>T;
	ll x,y,z;
	for(ll i=1;i<=n;i++)cin>>c[i];
	for(ll i=1;i<=m;i++){
		cin>>x>>y>>z;add(x,y,z);add(y,x,z);
	}
	spfa(1);
	init();
	for(ll i=1;i<=n;i++)chang(i);
	ll ans=-0x3f3f3f3f;
	dfs(1,0);
	for(ll i=1;i<=n;i++){
		ans=max(ans,siz[i]*dlt[i]);
	}
	cout<<max(ans,0ll)<<'\n';//dlt可能为负数，但答案至少为0 
	return 0;
}