题解 P5201 【[USACO19JAN]Shortcut G】

· · 题解

可以理解为最短路树板子题？

既然题目要求最短路那么肯定先求出每一个点到 1 的最短路（dijkstra），然后把所有奶牛的路径画出来——我告诉你，这是一棵树（建议手画一下）。

为什么呢？因为既然每条奶牛的路径是定了的，所以每条奶牛到 1 的路径是唯一的，当然是树，是以 1 为根的树。

这不就简单了嘛，对于每一个节点 u，设 u 到 1 的最短路是 d_u，那么如果我们连接 (u,1) 获得的利益是 \max \{0,(d(u)-t)\times s(u)\}，其中 s 为 u 在最短路树中的子树的奶牛总数量。为什么呢？因为只有这个节点子树内的奶牛的路径会缩短。

最后我们看代码。代码中变量有一点点小混乱 a_i 代表每个节点的奶牛数量，c_i 代表走到 i 的奶牛下一步去哪里。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
const int N=10009,M=50009;

struct edge {int to,nxt,w;}e[M*2][2]; int hd[N][2],tot;
void add(int u,int v,int w,bool type) {
    e[++tot][type]=(edge){v,hd[u][type],w}; hd[u][type]=tot;
}

struct node {
    int u,val;
    bool operator < (const node &b) const {
        return val>b.val;
    }
};
int d[N];
void dijkstra(int n) {
    priority_queue<node>q; memset(d,0x3f,sizeof(d));
    q.push((node){n,d[n]=0});
    while(!q.empty()) {
        int u=q.top().u; q.pop();
        for(int i=hd[u][0],v;i;i=e[i][0].nxt) {
            v=e[i][0].to;
            if(d[v]>d[u]+e[i][0].w)
                d[v]=d[u]+e[i][0].w, q.push((node){v,d[v]});
        }
    }
}

int n,m,t,a[N],c[N],s[N],ans;

void dfs(int u,int fa) {
    s[u]=a[u];
    for(int i=hd[u][1],v;i;i=e[i][1].nxt) {
        if((v=e[i][1].to)==fa) continue;
        dfs(v,u);
        s[u]+=s[v];
    }
    ans=max(ans,s[u]*(d[u]-t));
}

signed main() {
    freopen("shortcut.in","r",stdin);
    freopen("shortcut.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&t);
    rep(i,1,n) scanf("%lld",&a[i]);
    rep(i,1,m) {
        int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w,0), add(v,u,w,0);
    }
    dijkstra(1);
    rep(u,1,n) for(int i=hd[u][0];i;i=e[i][0].nxt) {
        int v=e[i][0].to;
        if(d[u]>d[v]) continue;
        if(d[u]+e[i][0].w==d[v]) {
            if(!c[v]) c[v]=u;
            else if(c[v]>u) c[v]=u;
        }
    }
    tot=0;
    rep(i,2,n) add(i,c[i],0,1),add(c[i],i,0,1);
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}