要问是否存在一个总权重为负数的环，用dfs即可解决。
time：33ms
#include <cstdio>
#include <cstring>
#define N 3000
using namespace std;
int n, m, T, w[N], u[N], v[N], next[N], first[N], pa[N], d[N], tag, i; void read_graph(void)
{
for(int e = ; e < m; e++)
{
scanf("%d%d%d",&u[e], &v[e], &w[e]);
next[e] = first[u[e]];
first[u[e]] = e;
}
}
void dfs(int x, int fa, int dis)
{
pa[x] = fa;
d[x] = dis;
for(int e = first[x]; e != -; e = next[e])
if(tag) return;
else if(pa[v[e]] == -)//这里应该改为pa[v[e]] != x ，要考虑到负权上的点可能事先被访问过，感谢提出
{
if(v[e] == i && d[x] + w[e] < )
{
puts("possible"), tag = ;
return ;
}
if(v[e] == i)
continue;
dfs(v[e], x, d[x] + w[e]);
}
}
int main(void)
{
scanf("%d", &T);
while(T--)
{
memset(first, -, sizeof(first));
tag = ;
scanf("%d%d", &n, &m);
read_graph();
for(i = ; i < n; i++)
{
memset(d, , sizeof(d)), memset(pa, -, sizeof(pa)),
dfs(i, -, );
if(tag)
break;
}
if(!tag)
puts("not possible");
}
return ;
}
或者采用bellman—ford算法判断负权回路，
第n次循环时，若d[y]>d[x] + w[i]，也就是能够继续松弛下去说明图中存在负权回路。
time：44ms速度还慢了一点，相比dfs
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF 0x0f0f0f0f
#define MAXN 1111
#define MAXM 2222
using namespace std; int d[MAXN];
int u[MAXM], v[MAXM], w[MAXM], next[MAXM], first[MAXM];
int t, n, m, e;
void read_graph(void)
{
scanf("%d%d",&n, &m);
for(e = ; e < m; e++)
{
scanf("%d%d%d",&u[e], &v[e], &w[e]);
next[e] = first[u[e]];
first[u[e]] = e;
}
}
void bellman_ford(void)
{
int i;
for(int k = ; k < n-; k++)
for(i = ; i < e; i++ )
{
int x = u[i], y = v[i];
if(d[x] < INF)
d[y] = min(d[y], d[x] + w[i]);
}
for(i = ; i < e; i++)
{
int x = u[i], y = v[i];
if(d[y] > d[x] + w[i])
{
puts("possible");
break;
}
}
if(i == e)
puts("not possible");
}
int main(void)
{
scanf("%d",&t);
while(t--)
{
memset(d, 0x0f, sizeof(d));
memset(first, -, sizeof(first));
d[] = ;
read_graph();
bellman_ford();
}
return ;
}
然后是spfa算法求解是否存在负权回路，通过判断顶点出队次数大于顶点数n，可知存在负权路，源点的time[0]应该初始化为1，其他的点每松弛一次，次数增加。
time：77ms竟然比bellman—ford，自己写的dfs倒是成了最快的了。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define MAXN 1111
#define MAXM 2222
using namespace std; struct edgeType{
int v, w;
edgeType(int a, int b):v(a), w(b){}
};
int n,m,t;
int time[MAXN], inq[MAXN], d[MAXN]; vector <edgeType> g[MAXN]; bool spfa(void)
{
queue <int> q;
time[] = ;
q.push();
inq[] = ;
while(!q.empty())
{
int x = q.front();
q.pop();
inq[x] = ;
for(int i = ; i < (int)g[x].size(); i++)
if(d[g[x][i].v] > d[x] + g[x][i].w)
{
d[g[x][i].v] = d[x] + g[x][i].w;
time[g[x][i].v]++;
if(time[g[x][i].v] == n + )
return false;
if(!inq[g[x][i].v])
{
q.push(g[x][i].v);
inq[g[x][i].v] = ;
}
}
}
return true;
}
int main(void)
{
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
int a, b, c;
memset(time, , sizeof(time));
memset(inq, ,sizeof(inq));
memset(d, 0x0f,sizeof(d));
d[] = ;
for(int i = ; i < MAXN; i++)
g[i].clear();
for(int i = ; i < m;i++)
{
scanf("%d%d%d", &a, &b, &c);
g[a].push_back(edgeType(b, c));
}
if(spfa())
puts("not possible");
else puts("possible");
}
return ;
}