首先先膜杜教orz

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

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

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

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

 

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

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

 

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

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          //对pair的一种有效快捷的利用#define fi first#define se second#define mp make_pairusing namespace std;typedef long long ll;const int maxn = 2222222;ll dis[maxn];int vis[maxn], ord[maxn], deep[maxn], sz[maxn];int p[maxn][22];//dij时用的堆set 
          
           
             > hs;//利用pair简化邻接表vector < pair
            
             > e[maxn];const ll inf = 1ll<<60;void Dijk(int S, int n){ for(int i = 1; i <= n; i++) dis[i] = inf, vis[i] = 0; dis[S] = 0; for(int i = 1; i <= n; i++) hs.insert(mp(dis[i], i)); for(int i = 0; i < n; i++) { int u = (hs.begin())->se; hs.erase(hs.begin()); vis[u] = 1; ord[i] = u; //求最短路时顺便得到拓扑序orz for(int j = 0; 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 = 20; i >= 0; i--) if(deep[p[v][i]] >= deep[u]) v = p[v][i]; if(u == v) return u; for(int i = 20; i >= 0; i--) if(p[v][i] != p[u][i]) u = p[u][i], v = p[v][i]; return p[u][0];}int n, m, s, u, v, w;int main(){ //freopen("a.txt", "r", stdin); cin>>n>>m>>s; for(int i = 1; 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][0] = 0; deep[s] = 1; //构建最短路图的过程并建立支配树 for(int i = 1; i <= n; i++) { int d = -1, u = ord[i]; for(auto p : e[u]) { if(dis[p.fi] + p.se == dis[u]) { if(d == -1) d = p.fi; else d = lca(d, p.fi); } } p[u][0] = d; deep[u] = deep[d]+1; for(int j = 1; j < 21; j++) p[u][j] = p[p[u][j-1]][j-1]; //动态更新公共祖先 } for(int i = 1; i <= n; i++) sz[i] = 1; int ret = 0; for(int i = n-1; i >= 1; i--) //按照拓扑序dp求最大值 { u = ord[i]; sz[p[u][0]] += sz[u]; if(dis[u] <= (1ll<<50)) ret = max(ret, sz[u]); } cout<
             
              <