CF757F 题解

· · 题解

题目传送门

思路

作为 CF2800 的紫题，这题的思维量还蛮大的，看洛谷上的题解全是支配树，鄙人技穷，不会，只能用其他方式来解决。

开局一个 Dijkstra，求出起点 s 到各点之间的距离。

求完之后仍是一脸懵，但当你把各个点的最短路径记录下来时，你会发现，这形状很想一棵树。

没错，这就是我们熟悉的最短路树。

最短路树

所谓最短路树无非是将起点到各个点的最短路径保存下来（注意，可能有多条最短路径，这都要保留下来），所构成的图叫做最短路树（注意这是一个有向无环图（DAG））。

缩点

又有人要问了，要这图有什么用呢?

不难发现，在这个 DAG 中，如果我们删去的点是它到起点必须经过的点，那如果这个点被删，起点到它这只能换边，那么它的最短路径一定会发生改变。

有点绕自己理解一下。

这样我们可以考虑将删掉它后会发生更改的点记录一下，在最后枚举一下这个点所有会被它影响的点的数量，求最大值即可。

那么如何缩点呢?

我们可以考虑拓扑。

拓扑排序

想到这一点，作者本人也走了许多弯路，最开始用的普通循环来实现缩点，结果发现无法满足无后效性的问题（需要考虑后效性的原因是：这个点缩完后，无法保证后续是否在缩其它点时会不会重复计算，然后会挂在第 14 个点上）。

言归正传，书接上文。

我们发现当出度唯一的点是会被起点到它的最短路径上的所有点限制的，但是如果出度 \ge 2 的点的多条路径没有都必须经过的点（起点除外），那么即使删去了一条最短路径上的点，它到起点的最短路径不会变。

同理，如果它到起点的路上必须经过某一个点，那这个点一删，它的最短路径必须改变。

原理已经讲完，但如何实现呢。

我们可以考虑并查集。

并查集

我们不难发现，如果能一步到达这个点的所有点（可以理解为这个点的父亲节点）都会在同一个点（不能是起点）删去后改变最短路长度，那么它也会被影响。

这启示我们可以拿个数组来统计当前这个点会在哪一个点删去后被影响。

到这里我们就不难想到用并查集来实现。

一些题外话

这道题卡了我一天，能思考到这真不容易，总共让作者交了 42 发：

不难发现作者始终因为后效性卡在了第 14 个点上，A 的那一刻是真的岔气了。

Code

#include <bits/stdc++.h>
#define inf 2e18
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld; 
typedef int praise_long_long;
namespace io {
    using namespace std;
    inline ll read() {
        char n=getchar();
        ll num=0,flag=1;
        while(n<'0'||n>'9') {
            if(n=='-') {
                flag=-1;
            }
            n=getchar();
        }
        while(n>='0'&&n<='9') {
            num=num*10+n-'0';
            n=getchar();
        }
        return num*flag;
    }
    inline void print(ll x) {
        if(x<0) {
            putchar('-');
            print(-x);
            return;
        }
        if(x==0) {
            return;
        }
        print(x/10);
        putchar((char)(x%10+'0'));
    }
}
using namespace io;
const ll N=3e5+5;
struct node {
    ll vl,wl;
};
bool operator < (node a,node b) {
    return a.wl>b.wl;
}
vector<node> v[N],g[N],e[N];
priority_queue<node> q;
ll n,m,s,dis[N],du[N],f[N],cnt[N],mx;
bool vis[N];
queue<ll> que;
ll find(ll x) {
    if(x==f[x]) {
        return x;
    }
    return f[x]=find(f[x]);
}
void dij(ll s) {
    q.push({s,0});
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()) {
        node d=q.top();
        q.pop();
        ll u=d.vl;
        vis[u]=0;
        for(auto it : v[u]) {
            ll wl=it.wl,vl=it.vl;
            if(dis[vl]>dis[u]+wl) {
                dis[vl]=dis[u]+wl;
                if(!vis[vl]) {
                    q.push({vl,dis[vl]});
                    vis[vl]=1;
                }
            }
        }
    }
}
void tosort() {
    for(ll i=1;i<=n;i++) {
        if(!du[i]) {
            que.push(i);
        }
    }
    while(!que.empty()) {
        ll d=que.front();
        que.pop();
        for(auto it : g[d]) {
            du[it.vl]--;
            if(!du[it.vl]) {
                que.push(it.vl);
                ll fa=-1;
                for(auto k : e[it.vl]) {
                    if(fa==-1) {
                        fa=find(k.vl);
                        continue;
                    }
                    if(fa!=find(k.vl)) {
                        fa=-1;
                        break;
                    }
                }
                if(fa==-1||d==s) {
                    continue;
                }
                cnt[fa]+=cnt[find(it.vl)];
                cnt[find(it.vl)]=0;
                f[find(it.vl)]=fa;
            }
        }
    }
}
void solve() {
    memset(dis,0x3f,sizeof(dis));
    for(ll i=0;i<N;i++) {
        cnt[i]=1;
    }
    cin>>n>>m>>s;
    cnt[s]=0;
    for(ll i=1;i<=m;i++) {
        ll ul,vl,wl;
        cin>>ul>>vl>>wl;
        v[ul].push_back({vl,wl});
        v[vl].push_back({ul,wl});
    }
    dij(s);
    for(ll i=1;i<=n;i++) {
        for(auto it : v[i]) {
            if(dis[it.vl]==dis[i]+it.wl) {
                g[i].push_back(it);
                e[it.vl].push_back({i,it.wl});
                du[it.vl]++;
            }
        }
        f[i]=i;
    }
    tosort();
    for(ll i=1;i<=n;i++) {
        if(dis[i]==dis[0]||i==s) {
            continue;
        }
        // cout<<i<<' '<<cnt[i]<<endl;
        mx=max(mx,cnt[i]);
    }
    cout<<mx;
}
praise_long_long main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T=1;
//  cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}
/**/