网站弹出窗口代码,软件开发平台的选择,网站帮助中心设计,网站ip指向列表题意#xff1a;
给你 n 个点#xff0c; m 条双向边#xff0c;求爆了某个点后#xff0c;从s出发的最短路距离#xff0c;会改变最多的数量。
分析#xff1a;
建出最短路树#xff08;DAG#xff09;之后#xff0c;在最短路树上跑一下支配树#xff0c;找出支…题意
给你 n 个点 m 条双向边求爆了某个点后从s出发的最短路距离会改变最多的数量。
分析
建出最短路树DAG之后在最短路树上跑一下支配树找出支配的点。答案就是爆支配点的收益即为该点支配的 size。上支配树模板即可。支配树教程oi-wiki 板子 支配树算法用的是 Lengauer-Tarjan简单讲一下首先是支配树里面的定义 u的半支配点 指的是dfn最小的v(vu) 满足v到u存在一条路径 路径中所有点dfn 都 u
两条定理对应的是函数 LengauerTarjan 里的写法
u的半支配点是 大于u的所有祖先的半支配点中最小的节点sdom(u) 到 u 路径中所有节点 v 都满足 sdom(v) sdom(u)则 idom(u) sdom(u)
代码
#include bits/stdc.h
#define N 200005using namespace std;struct MAP {struct Edge {int x, y, nex;long long d;} edge[N * 5];int len, fir[N];void init(){len 0;memset(fir, -1, sizeof fir);}void addEdge(int x,int y){len; edge[len].xx; edge[len].yy; edge[len].nex fir[x]; fir[x] len; }void addEdge(int x, int y, long long d){len; edge[len].xx; edge[len].yy; edge[len].dd; edge[len].nexfir[x]; fir[x]len;}
};
MAP input;
MAP G, GF;
MAP dfsTree, dfsTreeF;
MAP dominate;queueint q;
bool vis[N];
long long dis[N];
int n, m, s;void SPFA()
{memset(vis, 0, sizeof vis);memset(dis, 126, sizeof dis);q.push(s);dis[s] 0;vis[s] 1;while (!q.empty()) {int x q.front();q.pop();vis[x] 0;for (int k G.fir[x]; k ! -1; k G.edge[k].nex) {int y G.edge[k].y;if (dis[y] dis[x] G.edge[k].d) {dis[y] dis[x] G.edge[k].d;if (!vis[y]) {vis[y] 1;q.push(y);}}}}
}struct DominatorTree {DominatorTree(){tot 0;}int id[N], dfn[N], fa[N], tot;int anc[N], sdom[N], mn[N];int in[N];int dp[N][21], dep[N];int idom[N];int dominateSize[N];int Find(int x) {if(x ! anc[x]) {int t anc[x];anc[x] Find(anc[x]);if(dfn[sdom[mn[x]]] dfn[sdom[mn[t]]]) {mn[x] mn[t];}}return anc[x];}void Dfs(int x) {dfn[x] tot;id[tot] x;for (int k G.fir[x]; k ! -1; k G.edge[k].nex) {int y G.edge[k].y;if (!dfn[y]) {Dfs(y);fa[y] x;dfsTree.addEdge(x, y);}}}void LengauerTarjan() {for(int i 1; i n; i) {anc[i] i;sdom[i] i;mn[i] i;}for(int i n; i 2; i--) {int x id[i];if(!x) continue;int pos i;for(int k GF.fir[x]; k ! -1; k GF.edge[k].nex) {int y GF.edge[k].y; // pre// if(!dfn[y]) continue;if(dfn[y] dfn[x]) {pos min(pos, dfn[y]);} else {Find(y); // find pos min(pos, dfn[sdom[mn[y]]]);}}sdom[x] id[pos];anc[x] fa[x];dfsTree.addEdge(sdom[x], x);}}int LCA(int x, int y) {if (dep[x] dep[y]) {swap(x, y);}int deep dep[x] - dep[y];for (int i 20; i 0; i--) {if (deep (1 i)) {deep - (1 i);x dp[x][i];}}if (x y) {return x;}for (int i 20; i 0; i--) {if (dp[x][i] ! dp[y][i]) {x dp[x][i];y dp[y][i];}}return dp[x][0];}void BuildDominate(int x) {int to dfsTreeF.edge[dfsTreeF.fir[x]].y;for(int k dfsTreeF.fir[x]; k ! -1; k dfsTreeF.edge[k].nex) {int y dfsTreeF.edge[k].y;to LCA(to, y);}idom[x] to;dep[x] dep[to] 1;dp[x][0] to;dominate.addEdge(to, x);for(int i 1; i 20; i) dp[x][i] dp[dp[x][i-1]][i-1];}void TopSort() {for (int x 1; x n; x) {for(int k dfsTree.fir[x]; k ! -1; k dfsTree.edge[k].nex) {int y dfsTree.edge[k].y;in[y] ;dfsTreeF.addEdge(y, x);}}for(int x 1; x n; x) {if(!in[x]) {in[x] ;dfsTree.addEdge(0, x);dfsTreeF.addEdge(x, 0);}}queueint q;q.push(0);while(!q.empty()) {int x q.front();q.pop();for(int k dfsTree.fir[x]; k ! -1; k dfsTree.edge[k].nex) {int y dfsTree.edge[k].y;in[y] --;if(in[y] 0) {q.push(y);BuildDominate(y);}}}}void DfsDominate(int x) {dominateSize[x] 1;for(int k dominate.fir[x]; k ! -1; k dominate.edge[k].nex) {int y dominate.edge[k].y;DfsDominate(y);dominateSize[x] dominateSize[y];}}void Run(int s) {dfsTree.init();dfsTreeF.init();dominate.init();Dfs(s);LengauerTarjan();TopSort();DfsDominate(s);}} dominatorTree;int main() {cin.tie(0);ios::sync_with_stdio(false);cin n m s;G.init();for (int i 1; i m; i) {cin input.edge[i].x input.edge[i].y input.edge[i].d;G.addEdge(input.edge[i].x, input.edge[i].y, input.edge[i].d);G.addEdge(input.edge[i].y, input.edge[i].x, input.edge[i].d);}SPFA();G.init();GF.init();for (int i 1; i m; i) {if (dis[input.edge[i].y] dis[input.edge[i].x] input.edge[i].d) {G.addEdge(input.edge[i].x, input.edge[i].y);GF.addEdge(input.edge[i].y, input.edge[i].x); } else if (dis[input.edge[i].x] dis[input.edge[i].y] input.edge[i].d) {G.addEdge(input.edge[i].y, input.edge[i].x);GF.addEdge(input.edge[i].x, input.edge[i].y);}}dominatorTree.Run(s);int res 0;for(int i 1; i n; i) {if(i s) continue;res max(res, dominatorTree.dominateSize[i]);}cout res endl;return 0;
}
