1971573_ce.cc

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

# include <stdio.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>
# define MAXN 100001
# define MAXM 1000001
# define INF 99999999999999

int visited[MAXN];
__int64 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;
	}
}

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

	s = tree->adjlist[v].firstedge;
	//system("pause");
	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 Output(Tree *G)
{
	long i;
	EdgeNode *s;

	for(i = 0; i < G->n; i++)
	{
		s = G->adjlist[i].firstedge;
		printf("%ld-",i);
		while(s)
		{
			printf("%ld-",s->adjvex);
			system("pause");
			s = s->next;
			system("pause");
		}
		
		printf("\n");
	}
}

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));
		memset(num,0,sizeof(num));
		for(i = 0; i < n; i++)
			scanf("%I64d",&num[i]);
		tree.n = n;tree.e = m;
		Inittree(&tree);
		CreateTree(&tree);
		//Output(&tree);
		//system("pause");
		dfs(&tree,0);
		__int64 min = INF, d;
		for(i = 1; i < n; i++)
			if((d=abs(num[i]-num[0]+num[i]))<min)
				min = d;
		printf("Case %d: %I64d\n",no++,min);
	}
}

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