缩点后，原图一定是DAG 另一层图复制的原图、新加的边从复制图层指向原图层，所以最后整张分层图都是DAG
by _Life_ @ 2021-06-02 19:20:35
@[aldol_reaction](/user/393190)
by _Life_ @ 2021-06-02 19:21:53
@[_Life_](/user/87434) 是从原图的指向点到新图的起始点连一条边，您似乎弄反了？应该是逆向边
by aldol_reaction @ 2021-06-02 19:25:01
@[aldol_reaction](/user/393190) az 确实弄反了
by _Life_ @ 2021-06-02 19:56:01
@[_Life_](/user/87434) 所以是不是啊QAQ 蒟蒻卡死了
by aldol_reaction @ 2021-06-02 20:02:43
@[aldol_reaction](/user/393190) 我是SPFA做的，但题解区确实有拓扑做法
by _Life_ @ 2021-06-02 21:15:37
@[_Life_](/user/87434) 86pts，不知道炸哪了qwq，dalao能帮忙看看嘛
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<set>
#define NDEBUG
#include<assert.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef unsigned int ui;
void chkmin(ll &x, ll y) {
if(y < x) x = y;
};
void chkmax(int &x, int y) {
if(y > x) x = y;
};
#define rep(i, a, n) for (int i=a;i<=n;i++)
#define per(i, n, a) for (int i=n;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define endl '\n'
#define pb push_back
#define mst(a, b) memset((a), (b), sizeof(a));
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod ((int)1e9+7)
#define maxn (int)(1e5 * 2+5)
int n, m, ans, S, val[maxn], in[maxn], dis[maxn];
vector <int> e[maxn], E[maxn];
bool vis[maxn];
void inp() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
e[x].pb(y);
}
}
struct event {
int pos, d;
event(int _pos = 0, int _d = 0) {
pos = _pos, d = _d;
}
friend bool operator < (event a, event b) {
return a.d > b.d;
}
};
int dis1[maxn], dis2[maxn];
int s[maxn], tot;
int dfn[maxn], low[maxn];
int scccnt, sccnum[maxn];
int dfscnt;
void tarjan(int u) {
dfn[u] = low[u] = ++dfscnt;
s[tot++] = u;
for(unsigned int i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(!sccnum[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
scccnt++;
do {
--tot;
sccnum[s[tot]] = scccnt;
++val[scccnt];
} while(s[tot] != u);
}
}
void build() {
// printf("scccnt = %d\n", scccnt);
for(int i = 1; i <= n; ++i) {
for(ui j = 0; j < e[i].size(); ++j) {
int from = i, to = e[i][j];
int u = sccnum[from], v = sccnum[to];
if(u != v) {
E[u].pb(v);
++in[v];
E[u + scccnt].pb(v + scccnt);
++in[v + scccnt];
E[v].pb(u + scccnt);
++in[u + scccnt];
// printf("%d %d\n%d %d\n%d %d\n",
// u, v, u + scccnt, v + scccnt, v, u + scccnt);
}
}
}
rep(i, 1, scccnt) val[i + scccnt] = val[i];
}
void spfa() {
queue<int> q;
q.push(sccnum[1]);//起点
for(int i=1; i<=2*tot; ++i) dis[i]=0;
dis[sccnum[1]]=0;
mst(vis, 0);
while(!q.empty()) {
int u=q.front();
q.pop();
vis[u]=0;
for(ui i = 0; i < E[u].size(); ++i) {
int v = E[u][i], w = val[u];
if(dis[v]<dis[u]+w) {
dis[v]=dis[u]+w;
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
}
}
void topo() {
bool flag = false;
queue<int> q;
for(int i = 1; i <= 2 * scccnt; ++i) {
if(!in[i]) q.push(i);
}
// printf("val[%d] = %d\n", S, val[S]);
// rep(i, 1, 2 * scccnt) printf("in[%d] = %d\n", i, in[i]);
while(!q.empty()) {
int u = q.front();
if(u == S) flag = true;
// printf("u = %d\n", u);
q.pop();
for(ui i = 0; i < E[u].size(); ++i) {
int v = E[u][i], w = val[u];
// printf("u = %d, in[%d] = %d\n", u, v, in[v]);
// if(flag) printf("OK");
--in[v];
if(flag) chkmax(dis[v], dis[u] + w);
if(!in[v]) q.push(v);
}
}
}
int main() {
inp();
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
build();
S = sccnum[1];
topo();
printf("%d\n", dis[S + scccnt]);
return 0;
}
by aldol_reaction @ 2021-06-02 21:26:01
已AC。拓扑排序的时候注意与1连通的点才能dp转移
by aldol_reaction @ 2021-06-02 21:50:03