洛谷 P3387 【テンプレート】縮点#
大佬のコードと比較してエラーを見つけた後、私は本当に以前にそれほど多くの点を通過できたことが奇跡だと思わずにはいられませんでした。
問題文#
n 個の頂点と m 本の辺を持つ有向グラフが与えられます。各頂点には重みがあり、最大の重みの和を持つパスを見つけてください。ただし、この重みの和だけを求めれば十分です。
入力形式:
1 行目には n と m が与えられます。
2 行目には n 個の整数が与えられます。それぞれの整数は頂点の重みを表します。
3 行目から m+2 行目まで、各行には 2 つの整数 u と v が与えられます。これは u から v への有向辺を表します。
出力形式:
最大の重みの和を 1 行で出力してください。
n≤10^4、m≤10^5、0≤頂点の重み≤1000
解法#
またまた長いテンプレート問題です。
tarjan の縮点と DAG dp という私が聞いたことのない操作ですね。
(またはメモ化再帰でもいいです)
もう二度とグラフを struct で書かないようにします、せいぜい namespace の中までです!!!
重複する辺はトポロジカルソートに影響しません
tarjan では、強連結成分のノードを探索木のルートノードの番号で彩色することで、トポロジカルソート時にこの i が本当に入次数がないのか、それともグラフに存在しないのかを判断するのに役立ちます。
コード#
#include<cstdio>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
class Tu {
public:
struct ed {
int to;
int nex;
};
void insert (int p1, int p2) {
++newp;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
int& operator[] (int &p) {
return w[p];
}
void tarjan (int p) {
dfn[p] = low[p] = ++tim;
s.push(p);
v[p] = 1;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (!dfn[y]) {
tarjan(y);
low[p] = min(low[p], low[y]);
}
else if (v[y]) {
low[p] = min(low[p], dfn[y]);
}
}
if (dfn[p] == low[p]) {
v[p] = 0;
color[p] = p;
while (s.top() != p) {
int y = s.top();
s.pop();
color[y] = p;
}
s.pop();
}
}
int topsort(int *cl) {
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (cl[i] == i && !in[i]) {
q.push(i);
f[i] = w[i];
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].nex) {
int y = e[i].to;
f[y] = max(f[y], f[u] + w[y]);
if (--in[y] == 0) {
q.push(y);
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(f[i], ans);
}
return ans;
}
ed e [MAXN];
int head[MAXN];
int newp, cnt;
int w[MAXN];
int color[MAXN];
int dfn[MAXN], low[MAXN], tim;
int out[MAXN], f[MAXN], in[MAXN];
bool v[MAXN];
stack<int> s;
} a, b;
int main (void) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
a.insert(x, y);
}
for (int i = 1; i <= n; ++i) {
if (!a.color[i]) a.color[i] = i;
if (!a.dfn[i]) {
a.tarjan(i);
}
}
for (int i = 1; i <= n; ++i) {
int u = a.color[i];
for (int j = a.head[i]; j; j = a.e[j].nex) {
int y = a.color[a.e[j].to];
if (u == y) continue;
b.insert(u, y);
++b.in[y];
}
}
for (int i = 1; i <= n; ++i) {
b.w[a.color[i]] += a.w[i];
}
printf("%d\n", b.topsort(a.color));
return 0;
}