思路:首先拓扑排序,把所有的环(注意是环,不是负环)找出来,然后用dfs遍历每个环,如果找到边权总和为负数的就输出 Yes ,否则输出 No
##Code:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int res, idu[N];
int n, m;
void add(int a, int b, int c)
{
e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx, idu[b] ++ ;
}
void topsort()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
if (!idu[i])
{
q.push(i);
st[i] = true;
}
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i; i = ne[i])
{
int j = e[i];
idu[j] -- ;
if (!idu[j])
{
q.push(j);
st[j] = true;
}
}
}
}
void dfs(int u)
{
for (int i = h[u]; i; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
st[j] = true;
res += w[i];
dfs(j);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
topsort();
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
res = 0;
dfs(i);
cout << res << endl;
if (res < 0)
{
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}