Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## bellman ford检查负圈, 注意M是双向边

Posted by SmartChen at 2018-10-30 17:34:03 on Problem 3259
```#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 510
#define MAXE 5210

int t, n, m, w, i, j, e;
int d[MAXN], ea[MAXE][3];

bool find_negative_loop(void){
fill(d, d + n + 2, 0);
for (i = 0; i < n; i++) {
for (j = 0; j < e; j++) {
//	printf("%d %d, %d %d %d\n", i, j, d[ea[j][1]], d[ea[j][0]] ,  d[ea[j][2]]);
if (d[ea[j][1]] > d[ea[j][0]] + ea[j][2]) {
d[ea[j][1]] = d[ea[j][0]] + ea[j][2];
if (i == n - 1)
return true;
}
}
}
return false;
}

int main() {
scanf("%d", &t);
while (t-- > 0) {
scanf("%d %d %d", &n, &m, &w);
m *= 2;
e = m + w;
for (i = 0; i < m; i++) {
scanf("%d %d %d", &ea[i][0], &ea[i][1], &ea[i][2]);
i++;
ea[i][0] = ea[i - 1][1];
ea[i][1] = ea[i - 1][0];
ea[i][2] = ea[i - 1][2];
}
for (; i < e; i++) {
scanf("%d %d %d", &ea[i][0], &ea[i][1], &ea[i][2]);
ea[i][2] = -ea[i][2];
}
if (find_negative_loop())
printf("YES\n");
else
printf("NO\n");
}
}
```

Followed by: