@[BigYellowDog](/space/show?uid=91681) QAQ 为啥要拓扑排序啊 dfs一下就好了呀
by NaCly_Fish @ 2019-02-04 22:09:50
@[NaCly_Fish](/space/show?uid=115864) dfs多简单qwq
by NaCly_Fish @ 2019-02-04 22:10:23
@[NaCly_Fish](/space/show?uid=115864) dalao窝发现我的问题就是在找答案的地方爆了，可否帮看一下QwQ
by Error_666 @ 2019-02-04 22:23:13
@[BigYellowDog](/space/show?uid=91681) 窝不会调bug QAQ 放过窝
by NaCly_Fish @ 2019-02-04 22:26:41
@[NaCly_Fish](/space/show?uid=115864) [传送门](https://www.luogu.org/recordnew/show/16069480)
窝窝窝A掉了... ...wa多亏了你说我拓扑那个地方，然后我就去看了。
发现，拓扑时用的边用去找答案了，然后就Wa了。蟹蟹啦～
发上我Debug无修改版的极丑代码QwQ
```cpp
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#define maxn 10005
#define maxm 100005
using namespace std;
stack<int> stak;
struct E {int next, to;} e[maxm], edge[maxm], ed[maxm];
int n, m, num, index, numm, cnt, ans, nummm;
int w[maxn], h[maxn], dfn[maxn], low[maxn], belong[maxn], hh[maxn], into[maxn], seq[maxn], f[maxn], hhh[maxn];
bool vis[maxn];
int read()
{
int x = 0; char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return x;
}
void add(int from, int to)
{
e[++num].next = h[from];
e[num].to = to;
h[from] = num;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++index;
stak.push(x), vis[x] = 1;
for(int i = h[x]; i != 0; i = e[i].next)
if(!dfn[e[i].to])
{
tarjan(e[i].to);
low[x] = min(low[x], low[e[i].to]);
}
else if(vis[e[i].to]) low[x] = min(low[x], dfn[e[i].to]);
if(dfn[x] == low[x])
while(1)
{
int y = stak.top(); stak.pop();
vis[y] = 0, belong[y] = x;
if(y == x) break;
w[x] += w[y];
}
}
void addAgain(int from, int to)
{
edge[++numm].next = hh[from];
edge[numm].to = to;
hh[from] = numm;
ed[++nummm].next = hhh[to];
ed[nummm].to = from;
hhh[to] = nummm;
}
void topsort()
{
queue<int> que;
for(int i = 1; i <= n; i++)
if(!into[i] && belong[i] == i)
que.push(i);
while(!que.empty())
{
int now = que.front(); que.pop(), seq[++cnt] = now;
for(int i = hh[now]; i != 0; i = edge[i].next)
{
into[edge[i].to]--;
if(!into[edge[i].to]) que.push(edge[i].to);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= m; i++)
{
int u = read(), v = read();
add(u, v);
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = h[i]; j != 0; j = e[j].next)
if(belong[i] != belong[e[j].to])
{
addAgain(belong[i], belong[e[j].to]);
into[belong[e[j].to]]++;
}
topsort();
for(int i = 1; i <= cnt; i++)
{
int x = seq[i];
for(int j = hhh[x]; j != 0; j = ed[j].next)
f[x] = max(f[x], f[ed[j].to]);
f[x] += w[x];
ans = max(ans, f[x]);
}
cout << ans;
return 0;
}
```
by Error_666 @ 2019-02-04 22:52:32