CF1000E We Need More Bosses

CF1000E We Need More Bosses

标题描述

标题大意：
给定一个 nnn 个点 mmm 条边的无向图，保证图连通。找到两个点s,ts,ts,t，使得sss到ttt必须经过的边最多（一条边无论走哪条路线都经过ta，这条边就是必须经过的边），2
<=n<=3
∗105,1<=m<=3
∗1052
<=n<=3
*10^5,1<=m<=3
*10^52
<=n<=3
∗105,1<=m<=3
∗105
输入格式

第一行两个整数，n,mn,mn,m
以下m行，每行两个整数x,yx,yx,y，表现xyxyxy间有一条无向边相连
输特殊式

一个整数，即最多的必须经过边数
感谢@守望 提供翻译
输入输出样例 #1

[size=3
]输入 #1

1. 5 5
2. 1 2
4. 2
5. 3
7. 3
8. 1
9. 4 1
10. 5 2

复制代码

[size=3
]输出 #1

1. 2

复制代码

输入输出样例 #2


[size=3
]输入 #2

1. 4 3
2. 1 2
3. 4 3
4. 3
5. 2

复制代码

[size=3
]输出 #2

1. 3

复制代码

思绪：

求下边的双连通性，然后找一条必经的最长路（标题中写的 sss 到 ttt 必须经过的边最多），也就是求全部桥的数目。
最长路就是缩点后树的直径，全部的边都是桥，求一下桥的数目就是最多的必须经过边数。
TarjanTarjanTarjan 算法求 EDCCEDCCEDCC，套模板

1. inline void add(int a, int b) {        e.push_back({b, h[a]});        h[a] = e.size() - 1;}void Tarjan(int u, int in_edge) {        low[u] = dfn[u] = &#43
2. ;&#43
3. ;tot;        stk.push(u);        for(int i = h[u]; ~i; i = e[i].ne) {                int v = e[i].v;                if(!dfn[v]) {                        Tarjan(v, i);                        low[u] = std::min(low[u], low[v]);                        if(low[v] > dfn[u]) bri[i] = bri[i ^ 1] = true; // 下个点的最小时间戳比当前点的时间戳大, 说明是桥                }else if(i != (in_edge ^ 1)) low[u] = std::min(low[u], dfn[v]); // 这条边不能是反向边        }        if(low[u] == dfn[u]) {                int v;                cnt&#43
4. ;&#43
5. ;;                do{                        v = stk.top();                        stk.pop();                        dcc[v] = cnt;                }while(v != u);        }}

复制代码

创建新的树：

1.     tree.resize(cnt &#43
2. ; 1);    Rep(u, 1, n &#43
3. ; 1) {            for(int i = h[u]; ~i; i = e[i].ne) {                    int v = e[i].v;                    if(bri[i]) { // 这条边是桥                            int nu = dcc[u], nv = dcc[v];                            if(nu == nv) continue; // 不能毗连相同编号                            tree[nu].push_back(nv);                            tree[nv].push_back(nu);                    }            }    }

复制代码

树的直径的求法：两段BFS，一段取恣意一个点找到一个间隔他最远的谁人点 uuu ，然后在从 uuu 开始找，找到间隔 uuu 最远的点 vvv ，这两个点之间的路径就是树的直径，也就是最长的间隔 s−>ts -> ts−>t。

1. inline int BFS(int root) {        dist.assign(cnt &#43
2. ; 1, INF);        q = std::queue<int>();        int max_num = root, max_dist = 0;        q.push(root);        dist[root] = 0;        while(!q.empty()) {                int u = q.front();                q.pop();                for(const int& v : tree[u]) {                        if(dist[v] == INF) { // 没走过                                dist[v] = dist[u] &#43
3. ; 1;                                if(dist[v] > max_dist) {                                        max_dist = dist[v];                                        max_num = v;                                }                                q.push(v);                        }                }        }        return max_num;}main：    // 计算树的直径    int u = BFS(1); // 这个点是恣意的    int v = BFS(u);

复制代码

然后找一下从 uuu 到 vvv 一共经过了多少边就是多少桥。

1. inline void BFS(int u, int v) { // 重载        dist.assign(cnt &#43
2. ; 1, INF);        q = std::queue<int>();        q.push(u);        dist[u] = 0;        while(!q.empty()) {                int now = q.front();                q.pop();                for(const int& ne : tree[now]) {                        if(dist[ne] == INF) {                                dist[ne] = dist[now] &#43
3. ; 1;                                q.push(ne);                        }                }        }        std::cout << dist[v] << &#3
4. 9;\n&#3
5. 9;;}

复制代码

Tarjan&#43
;树的直径Tarjan &#43
; 树的直径Tarjan&#43
;树的直径 ACcode:AC code:ACcode:

1. #include <iostream>#include <climits>#include <limits>#include <vector>#include <queue>#include <stack>typedef unsigned long long ull;typedef long long ll;typedef long double ld;typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i&#43
2. ;&#43
3. ;)#define Rep(i, len, n) for(int i = len; i < n; i&#43
4. ;&#43
5. ;)#define MAX_INT 0x7fffffff#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();struct edge {        int v, ne;};int n, m, tot = 0, cnt = 0;std::vector<edge> e;std::vector<std::vector<int>> tree;std::vector<int> low, dfn, bri, h, dcc, dist;std::stack<int> stk;std::queue<int> q;inline void add(int a, int b) {        e.push_back({b, h[a]});        h[a] = e.size() - 1;}void Tarjan(int u, int in_edge) {        low[u] = dfn[u] = &#43
6. ;&#43
7. ;tot;        stk.push(u);        for(int i = h[u]; ~i; i = e[i].ne) {                int v = e[i].v;                if(!dfn[v]) {                        Tarjan(v, i);                        low[u] = std::min(low[u], low[v]);                        if(low[v] > dfn[u]) bri[i] = bri[i ^ 1] = true;                }else if(i != (in_edge ^ 1)) low[u] = std::min(low[u], dfn[v]);        }        if(low[u] == dfn[u]) {                int v;                cnt&#43
8. ;&#43
9. ;;                do{                        v = stk.top();                        stk.pop();                        dcc[v] = cnt;                }while(v != u);        }}inline int BFS(int root) {        dist.assign(cnt &#43
10. ; 1, INF);        q = std::queue<int>();        int max_num = root, max_dist = 0;        q.push(root);        dist[root] = 0;        while(!q.empty()) {                int u = q.front();                q.pop();                for(const int& v : tree[u]) {                        if(dist[v] == INF) { // 没走过                                dist[v] = dist[u] &#43
11. ; 1;                                if(dist[v] > max_dist) {                                        max_dist = dist[v];                                        max_num = v;                                }                                q.push(v);                        }                }        }        return max_num;}inline void BFS(int u, int v) { // 重载        dist.assign(cnt &#43
12. ; 1, INF);        q = std::queue<int>();        q.push(u);        dist[u] = 0;        while(!q.empty()) {                int now = q.front();                q.pop();                for(const int& ne : tree[now]) {                        if(dist[ne] == INF) {                                dist[ne] = dist[now] &#43
13. ; 1;                                q.push(ne);                        }                }        }        std::cout << dist[v] << &#3
14. 9;\n&#3
15. 9;;}int main(void) {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr), std::cout.tie(nullptr);        std::cin >> n >> m;        low.resize(n &#43
16. ; 1);    dfn.resize(n &#43
17. ; 1);    dcc.resize(n &#43
18. ; 1);    h.resize(n &#43
19. ; 1, -1);    bri.resize(2
20. * m &#43
21. ; 1, false);    rep(i, m) {            int x, y;            std::cin >> x >> y;            add(x, y);            add(y, x);    }    Rep(i, 1, n &#43
22. ; 1) if(!dfn[i]) Tarjan(i, -1);           if(cnt <= 1) {                   std::cout << 0 << &#3
23. 9;\n&#3
24. 9;;                   return 0;           }    tree.resize(cnt &#43
25. ; 1);    Rep(u, 1, n &#43
26. ; 1) {            for(int i = h[u]; ~i; i = e[i].ne) {                    int v = e[i].v;                    if(bri[i]) {                            int nu = dcc[u], nv = dcc[v];                            if(nu == nv) continue;                            tree[nu].push_back(nv);                            tree[nv].push_back(nu);                    }            }    }    // 计算树的直径    int u = BFS(1);    int v = BFS(u);    BFS(u, v);    return 0;}

复制代码

一些标题：
Q:为什么 u 到 v 是必经过的最长路径（树的直径）?
A:
代码中通过两次 BFS 来求树的直径。起首从恣意一个点（这里是 1）开始举行 BFS，找到离这个点最远的点 u。然后从 u 点再次举行 BFS，找到离 u 最远的点 v。
根据树的直径的性子，对于一棵树，从恣意一个点出发找到的最远点肯定是直径的一个端点。以是第一次 BFS 找到的 u 是直径的一个端点。然后从 u 出发再次举行 BFS 找到的 v 就是直径的另一个端点。
如许 u 到 v 的路径就是这棵树的直径，由于树的直径界说为树中恣意两点间间隔的最大值，而通过上述两次 BFS 的方法保证了找到的 u 和 v 之间的路径是树中最长的路径。
Q:在原图中的意义（边双连通分量的角度）?
A:在原图中，边双连通分量内部是没有桥的，而桥毗连了不同的边双连通分量。通过求缩点后树的直径，实际上是找到了原图中通过桥毗连的两个最远的边双连通分量。u 到 v 的路径上经过的桥是原图中毗连不同边双连通分量的关键路径。
Q:树的直径（u 到 v 的路径）在原图中的意义是：
A:最长的桥路径：直径路径上的边都是原图中的桥，这条路径是原图中通过桥毗连的最长路径。
必经的关键路径：在原图中，如果要从一个边双连通分量到达另一个边双连通分量，必须通过它们之间的桥。直径路径代表了原图中最远的两个边双连通分量之间的必经之路。
Q:为什么这就是标题标解？
A:直径路径上的桥是原图中毗连不同边双连通分量的关键路径。
任何凌驾多个边双连通分量的路径都必须经过这些桥。因此，树的直径长度就代表了原图中两个最远的边双连通分量之间的最短路径长度（由于每次凌驾一个桥算一步）。

3
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。