Codeforces Round #391 div1 757F (Dominator Tree)

首先先膜杜教orz

这里简单说一下支配树的概念

支配树是对一个有向图来讲的

规定一个起点s，如果s到v的路径上必须经过某些点u，那么离s最近的点u就是v的支配点

在树上的关系就是，v的父亲是u。

一般图的支配树需要使用tarjan算法，但是如果有向图是没有环的，可以采用另一种做法

按照拓扑序建立支配树，每次加点的时候，枚举能到它的所有点，求它们在当前支配树的最近公共祖先，那个点就是该点的支配点

这个题先建立一个最短路图，易知，这个图是没有环的有向图，所以建立支配树的时候就可以采用以上做法

orz 膜杜教代码，写得太飘逸了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

//对pair的一种有效快捷的利用

#define fi first

#define se second

#define mp make_pair

using namespace std;

typedef long long ll;

const int maxn = ;

ll dis[maxn];

int vis[maxn], ord[maxn], deep[maxn], sz[maxn];

int p[maxn][];

//dij时用的堆

set <pair<ll, int> > hs;

//利用pair简化邻接表

vector < pair<int, ll>> e[maxn];

const ll inf = 1ll<<;

void Dijk(int S, int n)

{

    for(int i = ; i <= n; i++) dis[i] = inf, vis[i] = ;

    dis[S] = ;

    for(int i = ; i <= n; i++) hs.insert(mp(dis[i], i));

    for(int i = ; i < n; i++)

    {

        int u = (hs.begin())->se; hs.erase(hs.begin());

        vis[u] = ; ord[i] = u; //求最短路时顺便得到拓扑序orz

        for(int j = ; j < e[u].size(); j++)

        {

            int v = e[u][j].fi;

            if(dis[v] > dis[u] + e[u][j].se)

            {

                hs.erase(mp(dis[v], v));

                dis[v] = dis[u] + e[u][j].se;

                hs.insert(mp(dis[v], v));

            }

        }

    }

}

int lca(int u, int v)   //二进制倍增求LCA

{

    if(deep[u] > deep[v]) swap(u, v);

    for(int i = ; i >= ; i--) if(deep[p[v][i]] >= deep[u]) v = p[v][i];

    if(u == v) return u;

    for(int i = ; i >= ; i--) if(p[v][i] != p[u][i]) u = p[u][i], v = p[v][i];

    return p[u][];

}

int n, m, s, u, v, w;

int main()

{

    //freopen("a.txt", "r", stdin);

    cin>>n>>m>>s;

    for(int i = ; i <= m; i++)

    {

        cin>>u>>v>>w;

        e[u].push_back(mp(v, w));

        e[v].push_back(mp(u, w));

    }

    Dijk(s, n);

    p[s][] = ; deep[s] = ;

    //构建最短路图的过程并建立支配树

    for(int i = ; i <= n; i++)

    {

        int d = -, u = ord[i];

        for(auto p : e[u])

        {

            if(dis[p.fi] + p.se == dis[u])

            {

                if(d == -) d = p.fi;

                else d = lca(d, p.fi);

            }

        }

        p[u][] = d; deep[u] = deep[d]+;

        for(int j = ; j < ; j++) p[u][j] = p[p[u][j-]][j-];    //动态更新公共祖先

    }

    for(int i = ; i <= n; i++) sz[i] = ;

    int ret = ;

    for(int i = n-; i >= ; i--)       //按照拓扑序dp求最大值

    {

        u = ord[i];

        sz[p[u][]] += sz[u];

        if(dis[u] <= (1ll<<)) ret = max(ret, sz[u]);

    }

    cout<<ret<<endl;

}