3149613_ac_672ms_320k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define INF 2100000000

int map[22][22];

char name[22][11];
int cnt, W;
int d, p, ans;
int pt[22], cost[22];

void prim(int n,int v)
{
	int i, j, k;
	int min;
	int lowcost[22];

	W = 0;
	for(i = 0; i < n; i++)
	{
		lowcost[i] = map[v][i]==0?INF:map[v][i];
	}
	lowcost[v] = 0;
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
		{
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
		}
		if(min == INF)
		{
			W = INF;
			break;
		}
		W += min;
		lowcost[k] = 0;
		for(j = 0; j < n; j++)
		{
			if(map[k][j]!=0&&map[k][j]<lowcost[j])
			{
				lowcost[j] = map[k][j];
			}
		}
	}
}

void dfs(int pos,int num)
{
	int i;

	if(num==0)
	{
		prim(cnt,0);
		if(W < ans)
		{
			ans = W;
		}
		return ;
	}
	for(i = pos; i <= d-num; i++)
	{
		map[pt[i]][0] = map[0][pt[i]] = cost[i];
		dfs(i+1,num-1);
		map[pt[i]][0] = map[0][pt[i]] = 0;
	}
}

void solve()
{
	int i;

	for(i = 0; i < cnt; i++)
	{
		map[0][i] = map[i][0] = 0;
	}
	dfs(0,p);
}

int getId(char str[])
{
	if(strcmp(str,"Park")==0)
		return 0;
	for(int i = 1; i < cnt; i++)
	{
		if(strcmp(str,name[i])==0)
			return i;
	}
	strcpy(name[cnt],str);
	return cnt++;
}

int main()
{
	int i, n, c;
	int ida, idb;
	char a[11], b[11];

	scanf("%d",&n);
	memset(map,0,sizeof(map));
	cnt = 1;
	d = 0;
	for(i = 0; i < n; i++)
	{
		scanf("%s%s%d",a,b,&c);
		ida = getId(a);
		idb = getId(b);
		if(ida==idb)
		{
			continue;
		}
		if(map[ida][idb]==0||map[ida][idb] > c)
		{
			if(ida==0||idb==0)
			{
				pt[d] = (ida==0?idb:ida);
				cost[d++] = c;
			}
			map[ida][idb] = map[idb][ida] = c;
		}
	}
	scanf("%d",&p);
	if(d <= p)
	{
		prim(cnt,0);
		ans = W;
	}
	else
	{
		ans = INF;
		solve();
	}
	printf("Total miles driven: %d\n",ans);
	return 0;
}