前言： 感觉每次遇到有向图或无向图的题都是比赛时候嫌自己写的太乱，写了一半就不想写了，赛后看别人的代码直接orz，也太简洁了，所以今天打算对之前做过的图的各种距离问题进行一个总结，以后做到跟图有关距离有关的问题也持续更新在这里了。
1.无向图的直径（模板） cf 1294f ： 题目链接 题意： 给你一个图，让你在这个图里选3个点，问你怎样选才能使得这三个点连线之间包含的边数最多，最后输出最多的边数，以及选的三个点。
思路： 最优方法是先选个直径再选个离直径最远的点作为这三个点，这样包含的边数肯定是最多的，可以用反证法证得，如果选了先选了两个不是直径的点，肯定没有选了直径的优，画一下图就知道了。另外要特别注意直径是整张图，也就是整张图是一个链的的情况要特判一下。 以下是模仿mike大神（orz）写的代码。
#include
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef pair
typedef vector
typedef vector
typedef vector
typedef long long i64;
typedef vector
typedef vector
typedef pair
typedef double ld;
template
template
int n;
vvi g;
vi p;
pii dfs(int v, int par = -1, int dist = 0) {
p[v] = par;
pii res = mp(dist, v);
for (auto to : g[v]) {
if (to == par) continue;
res = max(res, dfs(to, v, dist + 1));
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("in", "r", stdin);
#endif
cin >> n;
g = vvi(n);
p = vi(n);
forn(i, n - 1) {
int v1, v2;
cin >> v1 >> v2;
--v1; --v2;
g[v1].eb(v2);
g[v2].eb(v1);
}
pii da = dfs(0);
pii db = dfs(da.se);
vi diam;
int v = db.se;
while (v != -1) {
diam.eb(v);
v = p[v];
}
if (int(diam.size()) == n) { //直径就是整个图，也就是整个图就是一条链
cout << n - 1 << '\n';
cout << diam[0] + 1 << " " << diam[1] + 1 << " " << diam.back() + 1 << '\n';
return 0;
}
queue
vi d(n, -1);
for (int u : diam) {
d[u] = 0;
q.push(u);
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (d[to] == -1) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
pii mx = mp(d[0], 0);
forn(i, n) {
mx = max(mx, mp(d[i], i));
}
cout << int(diam.size()) - 1 + mx.fi << '\n';
cout << diam[0] + 1 << " " << diam.back() + 1 << " " << mx.se + 1 << '\n';
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
2.DAG(有向无环图)的最长距离 计蒜客 a1254 题目链接
题意： 给你一个编号由(1~n)的有向图，给你m条有向边，形不成环（因为题目说了一条合法路的两点高度严格单调递减）， 现在问你这个DAG上最长的距离。
思路： 拓扑排序模板题，用个dp数组保存一下到达每个点的最长距离即可。
#include
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef pair
typedef vector
typedef vector
typedef vector
typedef long long i64;
typedef vector
typedef vector
typedef pair
typedef double ld;
template
template
const int maxn = (int)1e4 + 1000;
int T, n, m, deg[maxn], dp[maxn];
vector< vector< pair
void toposort() {
queue
forn(i, n) if (!deg[i]) q.push(i);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto it : g[v]) {
if (it.fi == v) continue;
--deg[it.fi];
if (!deg[it.fi]) q.push(it.fi);
dp[it.fi] = max(dp[it.fi], dp[v] + it.se);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("in", "r", stdin);
#endif
cin >> T;
while (T--) {
cin >> n >> m;
ms(dp, 0);//while(T--) + memset --maybe--> TLE
ms(deg, 0);
g = vector< vector< pair
forn(i, m) {
int v1, v2, val;
cin >> v1 >> v2 >> val;
--v1; --v2;
++deg[v2];
g[v1].pb({v2, val});
}
toposort();
int ans = -1;
forn(i, n) {
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
3.有向有环图的最长距离（每个点只有一条出边） 牛客寒假训练营第六场 B题目链接 题意： 给你n个点（编号为1~n），下面n行，第i行的数表示第i个点出边的终点，可能形成环，问你最长距离是多少
思路： 先用拓扑排序把能到的最远距离（用dp数组存）都求出来，然后再对入度仍不为0，也就是环内的点跑个dfs看一下这个环包含几个点（用circle数组存），最后如果这个点在环里，那就ans = max（ans, dp[i] + circle[i]）,如果不在环里，就是ans = max(ans, dp[i]);
#include
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef pair
typedef vector
typedef vector
typedef vector
typedef long long i64;
typedef vector
typedef vector
typedef pair
typedef double ld;
template
template
const int maxn = (int)1e6 + 1000;
int n, to[maxn], indeg[maxn], dp[maxn];
int dep[maxn], circle[maxn];
void dfs(int v, int d) {
if (circle[v]) return;
if (dep[v] != -1) circle[v] = d - dep[v]; //之前被访问过 形成一个circle
else dep[v] = d;
dfs(to[v], d + 1);
}
void toposort() {
queue
forn(i, n) if (!indeg[i]) q.push(i);
while (!q.empty()) {
int v = q.front();
q.pop();
--indeg[to[v]];
if (!indeg[to[v]]) q.push(to[v]);
dp[to[v]] = max(dp[to[v]], dp[v] + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("in", "r", stdin);
#endif
cin >> n;
ms(indeg, 0);
ms(dp, 0);
ms(dep, -1);
ms(circle, 0);
forn(i, n) {
cin >> to[i];
--to[i];
++indeg[to[i]];
}
toposort();
forn(i, n) if (indeg[i] && !circle[i]) dfs(i, 0);
int ans = -1;
forn(i, n) {
if (circle[i]) ans = max(ans, dp[i] + circle[i]);
else ans = max(ans, dp[i]);
}
cout << ans << '\n';
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
4.树上最大权值和子链（带负权） 牛客小白月赛题目链接 题意： 给你n个点，每个点都有一个权值，然后给你（n-1）条边， 每条链的值是链上所有点的权值之和，现在让你求最大权值和的子链。
思路： dfs 注意是双向边，如果用前向星要开两倍数组。
/**
* Copyright(c)
* All rights reserved.
* Author : zzy
* Date : 2020-03-09-17.36.43
*/
#include
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())
using namespace std;
typedef pair
typedef vector
typedef vector
typedef vector
typedef long long i64;
typedef vector
typedef vector
typedef pair
typedef double ld;
template
template
const int maxn = (int)1e6 + 5;
i64 n, a[maxn], head[maxn], tot, ans, big[maxn];
struct Edge{
int to, nxt;
}edge[maxn];
void addEdge(int u, int v) {
edge[tot].to = v;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void dfs(int u, int par) {
i64 mx = 0;
big[u] = a[u];
ans = max(ans, big[u]);
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == par) continue;
dfs(v, u);
ans = max(ans, mx + big[v] + a[u]);
mx = max(mx, big[v]);
}
big[u] = mx + a[u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
tot = 0;
ms(head, -1);
ans = LLONG_MIN;
cin >> n;
for1(i, n) cin >> a[i];
forn(i, n-1) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
cout << ans << '\n';
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
5.关于子链的问题（每条边的贡献） 题目链接 题意： 有n-1条边，现在可以将1~n-1这n-1个数赋值给这n-1条边作为他们的值，现在定义这棵树的权值为所有子链的值之和，问你这棵树的最小权值。
思路： 有很多条子链不好搞，自然想到考虑每条边的贡献度，每条边在计算树的权值时出现的次数为他左边一共有多少个点*右边一共有多少个点，搞个dfs记录一下右边的点的个数x，n-x就是左边点的个数，那么x*（n-x）就是这条边的贡献，因为要最小排序，所以把这n-1条边的贡献从大到小排序，按1~n-1依次赋值给各个边计算结果就ok。
对了，比赛中想这题的时候突然想到之前cf上的一道题：添加链接描述 给你两个点a,b，问你有多少组（x,y）x≠a,x≠b,y≠a,y≠b 之间的路径并经过ab这条路，思路也是先把a连得路全都搞没了，bfs一下，看有几个点到不了，再把b连得路全都搞没了，bfs一下，看有几个点到不了，然后这两个数相乘就ok。
ac代码：
/**
* Think twice, code once.
* 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
* 2.runtime error
* 3.boundary condition
* ---------------------------------------------------------------------------------------
* Author : zzy
* Date : 2020-03-22-02.47.18 Saturday
*/
#include
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())
using namespace std;
typedef pair
typedef vector
typedef vector
typedef vector
typedef long long i64;
typedef vector
typedef vector
typedef pair
typedef double ld;
template
template
const i64 maxn = (i64)1e5+1000;
i64 n, rt[maxn];
vvi64 g(maxn);
vi64 e;
void dfs(int u, int par) {
rt[u] = 1;
for (int to : g[u]) {
if (to == par) continue;
dfs(to, u);
rt[u] += rt[to];
}
if (par) e.eb(rt[u]*(n-rt[u]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
cin >> n;
forn(i, n-1) {
int u, v;
cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
}
dfs(1, 0);
sort(all(e), [&](i64 n1, i64 n2) {
return n1>n2;
});
i64 ans = 0;
forn(i, n-1) {
ans += (i+1)*e[i];
}
cout << ans << '\n';
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}