此题是求出现负权回路的吗？
我的想法是求负权回路，若出现负权回路则输出YES，否则NO。
不知是否是我的想法错误还是代码写错，请大牛帮忙看看。
#include <iostream>
#include <cstdio>

using namespace std;

int n;
int d[1001],g[1001][1001];

int main ()
{
	int t,i,j,m,w,k,x,y,z,s;
	bool flag;
	scanf ("%d",&t);
	while (t--)
	{
		scanf ("%d%d%d",&n,&m,&w);
		memset (g,10001,sizeof (g));
		for (i = 1; i <= n; i++)
			g[i][i] = 0;
		for (i = 0; i < m; i++)
		{
			scanf ("%d%d%d",&x, &y, &z);
			g[x][y] = z;
			g[y][x] = z;
		}
		flag = false;
		for (i = 0; i < w; i++)
		{
			scanf ("%d%d%d",&x,&y,&z);
			if (z > g[x][y])
				flag = true;
			g[x][y] = 0 - z;
		}
		if (flag)
			printf ("YES\n");
		else
		{
			for (s = 1; s <= n; s++)//穷举所有顶点
			{
				for (i = 1; i <= n; i++)
					d[i] = 10001;
				d[s] = 0;
				for (k = 1; k < n; k++)//做一次bellman_ford
				{
					for (i = 1; i <= n; i++)
						for (j = 1; j <= n; j++)
							if (d[j] > d[i] + g[i][j])
								d[j] = d[i] + g[i][j];
				}
				flag = false;
				for (i = 1; i <= n; i++)
					for (j = 1; j <= n; j++)
						if (d[j] > d[i] + g[i][j])
						{
							flag = true;
							break;
						}
				if (flag)
				{
					break;
				}
			}
			if (s > n)
				printf ("NO\n");
			else
				printf ("YES\n");
		}
	}
	return 0;
}

• 貌似用顶点g【i】【j】写的bellman不行呀，一定要用结构体表示才行呀！郁闷…… (0) zhuxian 2009-06-21 10:07:58