题解 P5201 【[USACO19JAN]Shortcut】

· · 题解

发现自己难题做多了，反不会简单题。

题目大意

给定一个有 n 个结点和 m 条边的带权无向图，每个结点 i 上有 c_i 头奶牛， 1 号结点为家，每次回家奶牛会走一条最短的路径，如果有多条长度相同的最短路径，则奶牛会走字典序最小的一条。现在，你可以增加一条从 1 到任意结点的长度为给定值 T 的一条边。如果一头奶牛在平时回家的路上经过了这条边相连的结点，且这条边能使其回家路径更短，则其会走这条边。求能使所有奶牛走的路径长度和的变化的最大值。

解题思路

从结点 1 开始做最短路，建出最短路树， DFS 遍历最短路树，对最短路树上的一点，其子树中的点在回家的过程中都会经过该点。此时若连接一条从该节点到 1 号结点的边，则其最短路长度总和会减少 siz\times(dist_x -T)) 。

建最短路树时，由于奶牛会在路径长度相等的情况下走字典序更小的路径，所以我的方法是 从小到大 枚举起点 x ，遍历出边设为指向 y ，如果满足最短路条件（即 dist_y=dist_x+edgeweight ）且这个点之前没有被其他节点连过（连过则一定更小更优），则连一条边，

注意 c_i 有可能是 0 。在 DFS 的过程中，不能按照 siz 的值判断是否访问过结点，而应增加一个附加数组，我被这个坑了好久。

请使用 long long 。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=100010;
typedef long long ll;
ll n,m,c[maxn],T,cur,h[maxn],nxt[maxn],p[maxn],w[maxn],u,v,t;
ll dist[maxn],siz[maxn],ans;
bool tf[maxn];
struct node
{
    ll id,v;
    bool operator<(node x)const{return v>x.v;}
};
priority_queue<node>q;
vector<int>g[10010];
void add_edge(ll u,ll v,ll t)
{
    cur++;
    nxt[cur]=h[u];
    h[u]=cur;
    p[cur]=v;
    w[cur]=t;
}
bool f[maxn];
void dfs(int x)
{
    siz[x]=c[x];f[x]=true;
    for(vector<int>::iterator it=g[x].begin();it!=g[x].end();it++)
    if(!f[*it])dfs(*it),siz[x]+=siz[*it];
    ans=max(ans,siz[x]*(dist[x]-T));
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&T);
    for(int i=1;i<=n;i++)scanf("%lld",c+i);
    while(m--)scanf("%lld%lld%lld",&u,&v,&t),add_edge(u,v,t),add_edge(v,u,t);
    q.push({1,0});
    while(!q.empty())
    {
        node x=q.top();q.pop();
        if(tf[x.id])continue;
        tf[x.id]=true;dist[x.id]=x.v;
        for(int j=h[x.id];j;j=nxt[j])q.push({p[j],x.v+w[j]});
    }
    memset(tf,0,sizeof tf);
    for(int i=1;i<=n;i++)for(int j=h[i];j;j=nxt[j])
    if(dist[p[j]]==dist[i]+w[j]&&!tf[p[j]])tf[p[j]]=true,
    g[i].push_back(p[j]),g[p[j]].push_back(i);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}