3058496_ac_93ms_288k.cpp

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

# include <stdio.h>
# include <stdlib.h>
# include <string>
# include <iostream>

using namespace std;

# define MAXV 201
# define MAXE 19901

typedef struct enode
{
	int v1;
	int v2;
	int weight;
}Edge;

Edge E[MAXE];
int ans;
int st, ed;

int cmp(const void *a, const void *b)
{
	struct enode *aa = (struct enode *)a;
	struct enode *bb = (struct enode *)b;
	return bb->weight-aa->weight;
}

void kruskal(Edge E[], int n, int e)
{
	int i, j;
	int m1, m2, sn1, sn2;
	int vest[MAXV];

	for(i = 0; i < n; i++)
		vest[i] = i;
	j = 0;
	while(vest[st]!=vest[ed])
	{
		m1 = E[j].v1; m2 = E[j].v2;
		sn1 = vest[m1]; sn2 = vest[m2];
		ans = E[j].weight;
		if(sn1!=sn2)
		{
			for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("%d tons\n\n",ans);
}

string name[201];
int num;

int get_id(string str)
{
	int i;

	for(i = 0; i < num; i++)
	{
		if(name[i]==str)
			return i;
	}
	name[num] = str;
	return num++;
}

void get_graph(int e)
{
	int i, w;
	string a, b;

	num = 0;
	for (i = 0; i < e; i++)
	{
		cin >> a >> b >> w;
		E[i].v1 = get_id(a);
		E[i].v2 = get_id(b);
		E[i].weight = w;
	}
	cin >> a >> b;
	st = get_id(a);
	ed = get_id(b);
}

int main()
{
	int cas;
	int n, e;

	cas = 1;
	while(scanf("%d%d",&n,&e)==2)
	{
		if(n==0&&e==0)
		{
			break;
		}
		printf("Scenario #%d\n",cas++);
		get_graph(e);
		qsort(E,e,sizeof(E[0]),cmp);
		kruskal(E,n,e);
	}
	return 1;
}