1344.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 64 行

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

int value[50][50];
int ans,n;
int del[50];

void calc()
{
	int i, j, temp, k, s;

	for( k=0; k< n-2; k++ )
	{
		s = 10000000;
		for( i = k+1; i < n; i++ )
		for( j = i+1; j < n; j++ )
		{
			if( (temp = (value[i][k]+value[j][k]-value[i][j])/2 ) < s )
				s = temp;
		}

		for( i = k+1; i < n; i++ )
			value[i][k] -= s, value[k][i] -= s;
		ans += s;
	}
	ans += value[n-2][n-1];
}

int main()
{
	int i, j;
	
	while( 1 )
	{
		scanf( "%d", &n );

		if( n == 0 ) break;

		for( i=0; i<n; i++ )
		{
			for( j=i+1; j<n; j++ )
			{
				scanf( "%d", &value[i][j] );
				value[j][i] = value[i][j];
			}

			value[i][i] = 0;
		}

		ans = 0;

		calc();

		printf( "%d\n",ans );
	}

	return 0;
}