游客 注册 | 登录
中文 | En

3991 - 龙哥治水

通过次数

0

提交次数

1

时间限制 : 1 秒 内存限制 : 128 MB
龙哥喜欢拼火柴是众所周知的事情，在他专心致志拼火柴时，从来不顾其他事。当他拼完火柴后发现，他种在地里的火柴被淹了（火柴就是种出来的怎么了？哼！），于是龙哥不得不修建水沟将自己农田的水排到池塘里去，其中n为水沟数，m为水沟之间交汇点的数目（1表示龙哥的农田，m表示池塘，即要将水从1引到m处）。当龙哥修完水沟后快快乐乐的去吃汉堡了，但是即便龙哥是万能的，也无法抵挡大自然的力量，每条水沟容水被限制了能够排水的量，即当排完一定量的水后当前水沟就作废了。吃着吃着龙哥突然很担心，生怕把池塘里的长者给淹到，于是想知道他的水沟最多能排多少水到池塘，可是龙哥由于吃撑了汉堡现在生活不能自理，那么请你们来帮他解决这个问题吧！

题目输入

测试数据有多组
第一行输入两个整数n, m（0 <= n <= 200, 2 <= m <= 200），表示水沟数和交汇点的数目；
接下来n行，每行3个整数a, b, c（1 <= a, b <= m, 0 <= c <= 10000000），分别表示此条水沟将a处的水引到b处，最大排水量为c

题目输出

输入一个整数，表示最大排入池塘的水量

输入/输出样例

输入格式

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

输出格式

50

C++解答

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define min(a,b) a<b?a:b
#define MAXDATA 9999999

typedef struct nd NODE ;

typedef struct edge
{
	NODE *begin ;
	NODE *end ;
	long long f ;
	long long c ;
	struct edge *bnext ;
	struct edge *enext ;
} EDGE ;

struct nd
{
	int data ;
	long long e ;
	int h ;
	EDGE *in ;
	EDGE *out ;
	struct nd *next ;
} ;

NODE *head ;
int n, m ;

void ini ()
{
	EDGE *ep = head->out ;
	
	while (ep)
	{
		ep->f = ep->c ;
		head->e -= ep->f ;
		ep->end->e += ep->f ;
		
		ep = ep->bnext ;
	}
}

void relabel (NODE *np)
{
	int minh = MAXDATA ;
	int isin ;
	EDGE *ep ;
	
	if (np->out != NULL)
	{
		ep = np->out ;
		isin = 0 ;
	}
	else
	{
		ep = np->in ;
		isin = 1 ;
	}
	
	while (ep != NULL)
	{
		if (!isin)
		{
			if (ep->f < ep->c && ep->end->h < minh)
				minh = ep->end->h ;
			
			if (ep->bnext != NULL)
				ep = ep->bnext ;
			else
			{
				ep = np->in ;
				isin = 1 ;
			}
		}
		else
		{
			if (ep->f > 0 && ep->begin->h < minh)
				minh = ep->begin->h ;
			
			ep = ep->enext ;
		}
	}
	
	np->h = minh + 1 ;
}

void push (NODE *np1, NODE *np2, EDGE *ep)
{
	int changef ;
	
	if (ep->begin == np1 && ep->end == np2)
	{
		changef = min (ep->c - ep->f, np1->e) ;
		ep->f += changef ;
	}
	else
	{
		changef = min (ep->f, np1->e) ;
		ep->f -= changef ;
	}
	
	np1->e -= changef ;
	np2->e += changef ;
}

void disch (NODE *np)
{
	int isin ;
	EDGE *ep ;
	if (np->out != NULL)
	{
		ep = np->out ;
		isin = 0 ;
	}
	else
	{
		ep = np->in ;
		isin = 1 ;
	}
	
	while (np->e > 0)
	{
		if (ep == NULL)
		{
			relabel (np) ;
			
			if (np->out != NULL)
			{
				ep = np->out ;
				isin = 0 ;
			}
			else
			{
				ep = np->in ;
				isin = 1 ;
			}
		}
		else if (((ep->f < ep->c && !isin) && (np->h == ep->end->h + 1)) || ((ep->f > 0 && isin) && (np->h == ep->begin->h + 1)))
		{
			if (!isin)
				push (np, ep->end, ep) ;
			else
				push (np, ep->begin, ep) ;
		}
		else
		{
			if (!isin)
			{
				if (ep->bnext != NULL)
					ep = ep->bnext ;
				else
				{
					ep = np->in ;
					isin = 1 ;
				}
			}
			else
				ep = ep->enext ;
		}
	}
}

void movend (NODE *np, NODE *up)
{
	if (up == NULL)
		return ;
	
	up->next = np->next ;
	np->next = head->next ;
	head->next = np ;
}

void getmaxf ()
{
	int i, oldh ;
	NODE *up = NULL ;
	head->h = n ;
	NODE *np = head->next ;
	ini () ;
	
	while (np->data != n)
	{
		oldh = np->h ;
		disch (np) ;
		
		if (np->h > oldh)
		{
			movend (np, up) ;
			up = NULL ;
		}
			
		if (up == NULL)
			up = head->next ;
		else
			up = up->next ;
		np = np->next ;
	}
}

NODE *getnode (int k)
{
	NODE *np = head ;
	
	while (np)
	{
		if (np->data == k)
			return np ;
		np = np->next ;
	}
	
	return NULL ;
}

int main (void)
{
	int i, a, b ;
	EDGE *ep ;	
	NODE *np ;

	while (scanf ("%d%d", &m, &n) != EOF)
	{
		head = NULL ;
		
		for (i=n; i>0; i--)
		{
			np = (NODE*) malloc (sizeof(NODE)) ;
			np->data = i ;
			np->next = head ;
			np->e = 0 ;
			np->h = 0 ;
			np->in = NULL ;
			np->out = NULL ;
			
			head = np ;
		}
		
		for (i=0; i<m; i++)
		{
			ep = (EDGE*) malloc (sizeof(EDGE)) ;
			ep->f = 0 ;
			
			scanf ("%d%d%lld", &a, &b, &ep->c) ;
			ep->begin = getnode (a) ;
			ep->end = getnode (b) ;
			ep->bnext = ep->begin->out ;
			ep->enext = ep->end->in ;
			ep->begin->out = ep ;
			ep->end->in = ep ;
		}
		
		getmaxf () ;
		np = getnode (n) ;
		
		printf ("%lld\n", np->e) ;
	}
	return 0 ;
}
请先登陆