pku2021.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct 
{
	int f, y, id;
} Node;

typedef struct 
{
	char name[20];
	int age;
} Peo;

Node nd[101];
Peo p[101];
int K;

int get_name_id(char *s)
{
	int i;
	for (i = 0; i < K; i++)
	{
		if (strcmp(p[i].name, s) == 0)
		{
			return i;
		}
	}
	strcpy(p[K].name, s);
	K++;
	return K - 1;
}

int get_id(int x)
{
	int root;
	if (nd[x].f == x)
	{
		return x;
	}
	root = get_id(nd[x].f);
	if (nd[x].f != root)
	{
		nd[x].y += nd[nd[x].f].y;
		nd[x].f = root;
	}
	return root;
}

int cp(const void *a, const void *b)
{
	Peo *aa = (Peo *)a;
	Peo *bb = (Peo *)b;
	if (aa->age != bb->age)
	{
		return bb->age - aa->age;
	}
	return strcmp(aa->name, bb->name);
}

void init()
{
	int i;
	memset(nd, 0, sizeof(nd));
	memset(p, 0, sizeof(p));
	for (i = 0; i < 101; i++)
	{
		nd[i].id = i;
		nd[i].f = i;
	}
}

int main()
{
	int T, t, N, agedis, id1, id2, i;
	char name1[20], name2[20];
	scanf("%d", &T);
	for (t = 1; t <= T; t++)
	{
		init();
		scanf("%d", &N);
		K = 0;
		for (i = 0; i < N; i++)
		{
			scanf("%s %s %d\n", name1, name2, &agedis);
			id1 = get_name_id(name1);
			id2 = get_name_id(name2);
			nd[id2].f = id1;
			nd[id2].y = agedis;
		}
		for (i = 0; i <= N; i++)
		{
			get_id(i);
		}
		for (i = 0; i <= N; i++)
		{
			p[i].age = 100 - nd[i].y;
		}
		qsort(p, N + 1, sizeof(p[0]), cp);
		printf("DATASET %d\n", t);
		for (i = 1; i <= N; i++)
		{
			printf("%s %d\n", p[i].name, p[i].age);
		}
	}
	return 0;
}