3433635_ac_94ms_1156k.cpp

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT (Edge *)malloc(sizeof(Edge))

int n;
int visited[10001];

typedef struct node
{
	int adj;
	int w;
	struct node *next;
}Edge;

struct Node
{
	Edge *head;
}pot[10001];

struct NODE
{
	int v;
}queue[10001];
int dis[10001][2];
int f, r;
int d[10001];
int max = -1;

void del(int a,int b)
{
	Edge *s;

	s = pot[a].head;
	while(s->next)
	{
		if(s->next->adj==b)
		{
			s->next = s->next->next;
			return ;
		}
		else
			s = s->next;
	}
}

void bfs()
{
	int i, v;
	Edge *s;

	f = r = -1;
	for(i = 0; i < n; i++)
		if(d[i]==1)
			queue[++f].v = i;
	while(f!=r)
	{
		++r;
		v = queue[r].v;
		s = pot[v].head;
		while(s->next)
		{
			if(dis[v][0]+s->next->w>dis[s->next->adj][1])
				dis[s->next->adj][1] = dis[v][0]+s->next->w;
			if(dis[s->next->adj][0]<dis[s->next->adj][1])
			{
				dis[s->next->adj][0] += dis[s->next->adj][1];
				dis[s->next->adj][1] = dis[s->next->adj][0]-dis[s->next->adj][1];
				dis[s->next->adj][0] = dis[s->next->adj][0]-dis[s->next->adj][1];
			}
			del(s->next->adj,v);
			d[v]--;d[s->next->adj]--;
			if(d[s->next->adj]==1)
				queue[++f].v = s->next->adj;
			s->next = s->next->next;
		}
	}
}

int main()
{
	int i;
	Edge *s;
	int st, ed, w;

	for(i = 0; i < 10000; i++)
	{
		pot[i].head = INIT;
		pot[i].head->next = NULL;
	}
	memset(d,0,sizeof(d));
	memset(dis,0,sizeof(dis));
	n = 1;
	while (scanf("%d%d%d",&st,&ed,&w) == 3)
	{
		st--,ed--;
		d[st]++,d[ed]++;
		s = INIT;
		s->adj = ed;s->w = w;
		s->next = pot[st].head->next;
		pot[st].head->next = s;
		s = INIT;
		s->adj = st;s->w = w;
		s->next = pot[ed].head->next;
		pot[ed].head->next = s;
		n++;
	}
	bfs();
	for(i = 0; i < n; i++)
		if(dis[i][0]+dis[i][1]>max)
			max = dis[i][0]+dis[i][1];
	printf("%d\n",max);
	return 0;
}