Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
bellman ford检查负圈, 注意M是双向边#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:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator