#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int size = 50;
int max( int a,int b)
{
	return a>b?a:b;
}
int min( int a, int b)
{
	return a<b?a:b;
}
struct node
{
	int id;
	char name[size];
}address[size];
const int INF = 999999999;
struct 
{
	int a, b;
	int val;
}value[size][size];
typedef int G[size][size];
G graph;
char name1[size], name2[size];

int stack[size];
int pre[size];
int n;
int m;
int val;
int total;
int k;//最大度
bool edge[size][size];
bool flag[size];
void init()
{
	for (int i=0; i<size ;i++)
		for (int j=0; j<size; j++)
			graph[i][j] = INF;
	memset( edge, false, sizeof(edge));
	total = 0;
}
void deal( char s1[], char s2[], int value)
{
	int id1=1, id2=1, i;
	if( strcmp( "Park", s1) == 0)
		id1 = 0;
	if( strcmp( "Park", s2) == 0)
		id2 = 0;
	if( id1 )
	{
		for (  i=1; i<=m; i++)
		{
			if( strcmp( s1, address[i].name) ==0)
			{
				id1 = i; break;
			}
		}
		if( i > m)
		{
			strcpy( address[++m].name, s1);
			address[m].id = m;
			id1 = m;
		}
	}
	if( id2 )
	{
		for ( i=1; i<=m; i++)
		{
			if( strcmp( s2, address[i].name)==0)
			{
				id2 = i; break;
			}
		}
		if( i > m )
		{
			strcpy( address[ ++m ].name, s2 );
			address[m].id = m;
			    id2 = m;
		}
	}
	graph[id1][id2] = graph[id2][id1] = value;
}

void prim( )
{
	int i, j;
	bool visited[100];
	memset( visited, false,sizeof(visited));
    memset( value, 0, sizeof( value ));
	int top = 0;
	int cost[100];
    for (i = 1; i <= m; i++)
	{
		cost[i] = graph[1][i];
		pre[i] = 1;
	}
    visited[1] = true;
	stack[top++] = 1;
	for (i=1; i < m; i++)
	{
		int min = INF, k = -1;
		for (j=1; j <= m; j++)
		  if( !visited[j] && cost[j] < min)
			  min = cost[j], k=j;
		for (j=0; j<top; ++j)
		{
			if( min > value[ stack[j] ][ pre[k] ].val )
			{
			  value[ stack[j] ][ k ].val = min;
		      value[ stack[j] ][ k ].a = pre[k];
			  value[ stack[j] ][ k ].b = k;
			  value[ k ][ stack[j] ] = value[ stack[j] ][ k ];
			}
		}
		visited[ k ] = true;
		total += min;
		stack[ top++ ] = k;
        edge[ pre[k] ][ k ] = edge[ k ][ pre[k] ] = true;
		for (j=1; j<=m; j++)
			if(!visited[j] && (graph[k][j] < cost[j] ) )
				cost[j] = graph[k][j], pre[j] = k;
	}
}
void dfs( int now )
{
	flag[now] = true;
	for ( int i=1; i <= m; i++)
	{
		if(flag[i])
			continue;
		if ( edge[i][now] || edge[now][i])
		{
			//pre[ i ] = now;
		    if( value[ now][0].val < graph[i][now] )
			{
				value[i][0].val = graph[i][now];
				value[i][0].a = now;
				value[i][0].b = i;
			}
			else
			{
				value[i][0] = value[now][0];
			}
			dfs( i );
			
		}
	}
}

int result( )
{
	int i, j;
	int minval=INF;
	int index;

	for (i=1; i<=m; i++)
	{
		if( graph[i][0] <INF && minval > graph[i][0] )
		{
			minval = graph[i][0];
			index = i;//先添加的第一条最小权值的边
		}
	}
	total += minval;
	edge[0][index] = edge[index][0] = 1;//表明这里的边已经添加到生成树里面
	/*for (i=1; i<=m; i++)
	{
		value[i][0] = value[0][i] = value[i][index];
	}
	pre[0] = i;*/
	int mininum ;
	int p1 = index;

	for (i = 2; i <= k && i <= m; i++)
	{
		
		mininum = INF;
		memset(flag, false, sizeof(flag));
		dfs( p1 );
		for (j = 1; j <= m; j++)
		{
			if( graph[j][0] != INF && !edge[j][0])//stand for there is an edge between them并且这条边还没有被添加
			{
			   if( graph[j][0] - value[j][0].val < mininum)
			   {
			      mininum =  graph[j][0] - value[j][0].val;//最少添删
			      p1 = j;
			   }
			}
		}
		edge[ p1 ][ 0 ] = edge[0][p1] = true;
		value[ p1][ 0 ].val =  0;
		edge[ value[p1][0].a ][ value[p1][0].b ] = false;
		edge[ value[p1][0].b ][ value[p1][0].a ] = false;
		if( mininum >= 0 )
			return total;
		total += mininum;
		
		
	}
	return total;
}

int main()
{
	freopen("in.txt","r",stdin);
	while (scanf("%d", &n) ==1)
	{
        m = 0;
		init();
		for (int i=0; i < n; i++)
		{
			scanf("%s%s%d", name1, name2, &val);
			deal( name1, name2, val);
		}
		scanf("%d",&k);
		prim();
		printf("Total miles driven: %d\n", result() );

	}
	return 0;
}
		


			

• Re:好心的大牛给我测试一下吧。WA快疯了。 (4603) 20074635 2009-11-26 14:12:14
• Re:好心的大牛给我测试一下吧。WA快疯了。 (11) 20074635 2009-11-26 14:12:48
• Re:好心的大牛给我测试一下吧。WA快疯了。 (11) 20074635 2009-11-26 14:12:50
  • Re:好心的大牛给我测试一下吧。WA快疯了。 (11) youxirenjian163 2010-04-25 22:33:50