> 无语了……找不到一个能去所有点的点就disjoint
> void solve(void)
> {
> 	int i, j, k, m;
> 	if(N == 1)
> 	{
> 		puts("1 0");
> 		return;
> 	}
> 	for(i = 0; i < N; i++)
> 	{
> 		for(j = 0; j < N; j++)
> 		{
> 			if(j != i)
> 			{
> 				for(k = 0; k < N; k++)
> 				{
> 					if(k != i && k != j)
> 					{
> 						int temp = dist[i][k] + dist[k][j];
> 						if(dist[i][k] > 0 && dist[k][j] > 0 && (dist[i][j] < 0 || dist[i][j] > temp))
> 						{
> 							dist[i][j] = temp;
> 						}
> 					}
> 				}
> 			}
> 		}
> 	}
> 	for(i = 0; i < N; i++)
> 	{
> 		for(j = 0; j < N; j++)
> 		{
> 			if(i != j && dist[i][j] < 0)
> 			{
> 				break;
> 			}
> 		}
> 		if(j < N)//这个点不能所有点都去
> 		{
> 			continue;
> 		}
> 		for(j = 0; j < N; j++)
> 		{
> 			if(j != i && dist[i][j] > dist[i][i])
> 			{
> 				dist[i][i] = dist[i][j];//dist[i][i]记最小值
> 			}
> 		}
> 	}
> 	k = -1;
> 	m = 0x7FFFFFFF;
> 	for(i = 0; i < N; i++)
> 	{
> 		if(dist[i][i] > 0 && dist[i][i] < m)
> 		{
> 			k = i;
> 			m = dist[i][i];
> 		}
> 	}
> 	if(k >= 0)
> 	{
> 		printf("%d %d\n", k + 1, m);
> 	}
> 	else
> 	{
> 		puts("disjoint");
> 	}
> }

• 最郁闷的事情发生了，循环顺序搞错了…… (0) frkstyc 2005-04-09 09:59:26
  • 呵呵，Floyd的第一层循环应该是中间节点 (0) TN 2005-04-09 10:00:23