Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator