1971723_ac_609ms_12584k.cpp

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

# include <stdio.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>
# define MAXN 100002
# define MAXM 1000002
# define INF 99999999999999 

int visited[MAXN];
double num[MAXN];
typedef struct node 
{
	long adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MAXN];
typedef struct ALtree
{
	AdjList adjlist;
	long n, e;
}Tree;

void CreateTree(Tree *tree)
{
	long i;
	long v1, v2;
	EdgeNode *s;

	for(i = 0; i < tree->e; i++)
	{
		scanf("%ld%ld",&v1,&v2);
		v1--;v2--;
		s = (EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex = v1;
		s->next = tree->adjlist[v2].firstedge;
		tree->adjlist[v2].firstedge = s;
		s = (EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex = v2;
		s->next = tree->adjlist[v1].firstedge;
		tree->adjlist[v1].firstedge = s;
	}
}

double dfs(Tree *tree,long v)
{
	EdgeNode *s;

	s = tree->adjlist[v].firstedge;
	visited[v] = 1;
	while(s)
	{
		if(visited[s->adjvex]==0)
			num[v] += dfs(tree,s->adjvex);
		s = s->next;
	}
	return num[v];
}

void Inittree(Tree *tree)
{
	long i;

	for(i = 0; i < tree->n; i++)
		tree->adjlist[i].firstedge = NULL;
}

void input()
{
	static int no = 1;
	long i, n, m;
	Tree tree;

	while(scanf("%ld%ld",&n,&m)==2&&(n||m))
	{
		memset(visited,0,sizeof(visited));
		for(i = 0; i < n; i++)
			scanf("%lf",&num[i]);
		tree.n = n;tree.e = m;
		Inittree(&tree);
		CreateTree(&tree);
		dfs(&tree,0);
		double min, d;min = INF;
		for(i = 1; i < n; i++)
			if((d=fabs(num[i]-num[0]+num[i]))-min<0)
				min = d;
		printf("Case %d: %.0lf\n",no++,min);
	}
}

int main()
{
	input();
	return 1;
}