题目描述
有向图 \(G\) 有 \(N\) 个点，\(M\) 条边，点 \(u\) 的点权为 \(A_u\)。
若存在三元组 \(a,b,c\) 使得 \(a\) 至 \(b\) 有一条边，\(b\) 至 \(c\) 有一条边，则连一条 \(a\) 至 \(c\) 的边。重复执行以上操作，直到不存在这样的三元组为止。
求其最长链长度及最长链上的最小点权和。
分析
不难发现，只要 \(a,c\) 连通，则能连一条 \(a\) 至 \(c\) 的边。
若 \(a,c\) 在一个强连通分量内：
因为强连通分量内部任意两点连通，一个强连通分量在上述操作后可变为完全子图。
显然可以从任意一点进入子图遍历所有点后从任意一点离开子图。即一个完全子图的最长链长度为子图的点数。
点权和为完全子图内部的点权之和。
即对于强连通分量 \(G(V,E)\)，最长链长度为 \(|V|\)，点权和为 \(\sum\limits_{u\in V}a_u\)。
若 \(a,c\) 不在一个强连通分量内：
显然 \(a\to b,b\to c\) 的长度大于 \(a\to c\)。所以最优决策不是走 \(a\to c\) 这条新连的边。这里可视为不连接 \(a,c\)。
以每个点的强连通分量编号进行建图。
显然缩点后组成的图是 DAG。否则这个大图可以构成一个新的强连通分量。
接下来便可以拓扑排序后跑 DAG 上最长链板子。
设 \(f_u\) 为以 \(u\) 为起点的最长链长度，\(g_u\) 为以 \(u\) 为起点的最长链的最小点权和。
则有转移方程 \(f_u=\max\{f_u,f_v+w_v\},(u,v)\in E\)。
显然当 \(f_u<f_v+w_v\) 时，\(g_u=g_v+w'_v\)。
而当 \(f_u=f_v+w_v\) 时，\(g_u=\min\{g_u,g_v+w'_v\}\)。
代码
请欣赏工程码风。
#include <bits/stdc++.h>
#include <algorithm>
#define int long long
const int maxn = 2e5 + 20;
const int inf = 2e18;
int n, m;
int a[maxn];
int dfn[maxn], low[maxn], dfncnt;
int scc[maxn], sz[maxn], val[maxn], sccidx;
int stack[maxn], top;
int inDeg[maxn];
int f[maxn], fval[maxn];
std::vector <int> topo;
struct graph {
struct edge {
int u, v, w, next;
};
int head[maxn], cnt;
edge e[maxn];
void add(int x, int y) {
e[++cnt].u = x, e[cnt].v = y, e[cnt].next = head[x], head[x] = cnt;
}
} g, p;
void tarjan(int u, graph &g) {
low[u] = dfn[u] = ++dfncnt;
stack[++top] = u;
for(int i = g.head[u]; i; i = g.e[i].next) {
int v = g.e[i].v;
if(!dfn[v]) tarjan(v, g), low[u] = std::min(low[u], low[v]);
else if(!scc[v]) low[u] = std::min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
sccidx++;
while(stack[top] != u) scc[stack[top--]] = sccidx, sz[sccidx]++;
scc[stack[top--]] = sccidx, sz[sccidx]++;
}
}
void getSCC(int n, graph &g) {
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i, g);
}
std::vector <int> topoSort(graph &g) {
std::queue <int> q;
std::vector <int> res;
for(int i = 1; i <= sccidx; i++)
if(inDeg[i] == 0) q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
res.push_back(u);
for(int i = g.head[u]; i; i = g.e[i].next) {
int v = g.e[i].v, w = g.e[i].w;
if(--inDeg[v] == 0) q.push(v);
}
}
return res;
}
void solve() {
int ans = 0, ansp;
sccidx = 0, dfncnt = 0, g.cnt = 0, p.cnt = 0, top = 0;
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]), g.head[i] = p.head[i] = val[i] = sz[i] = dfn[i] = scc[i] = 0;
for(int i = 1; i <= m; i++) {
int x, y;
scanf("%lld %lld", &x, &y);
g.add(x, y);
}
getSCC(n, g);
for(int i = 1; i <= n; i++) {
for(int j = g.head[i]; j; j = g.e[j].next) {
int v = g.e[j].v;
if(scc[i] == scc[v]) continue;
p.add(scc[i], scc[v]);
inDeg[scc[v]]++;
}
}
for(int i = 1; i <= n; i++)
val[scc[i]] += a[i];
topo = topoSort(p);
for(int i = 1; i <= sccidx; i++) {
if(inDeg[i] == 0) fval[i] = val[i], f[i] = sz[i];
else fval[i] = inf;
}
for(auto u : topo) {
for(int i = p.head[u]; i; i = p.e[i].next) {
int v = p.e[i].v, w = sz[v];
if(f[v] < f[u] + w) f[v] = f[u] + w, fval[v] = fval[u] + val[v];
else if(f[v] == f[u] + w) fval[v] = std::min(fval[v], fval[u] + val[v]);
}
}
for(int i = 1; i <= n; i++)
if(ans < f[i]) ans = f[i], ansp = fval[i];
else if(ans == f[i]) ansp = std::min(ansp, fval[i]);
printf("%lld %lld\n", ans, ansp);
}
signed main() {
int t;
scanf("%lld", &t);
while(t--) solve();
return 0;
}