2945532_tle.cc

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

#include <stdio.h>
#include <vector>
#include <algorithm>
#define MaxV 20011

using namespace std;

int n, m, ans;
struct edge
{
	int id;
	int c;
};

vector <edge> graph[MaxV];
int que[1000001];
int f, r;

int bfs()
{
	int i, p, t;
	int mark = 0;
	int pre[MaxV], visited[MaxV];
	int F[MaxV], C;

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;pre[0] = -1;
	que[++r] = 0;
	C = 2100000000;
	while(f!=r)
	{
		f++;
		p = que[f];
		for(i = 0; i < graph[p].size(); i++)
		{
			t = graph[p][i].id;
			if(!visited[t]&&graph[p][i].c)
			{
				visited[t] = 1;
				que[++r] = t;
				pre[t] = p;
				F[t] = graph[p][i].c;
				if(t==n+1)
				{
					mark = 1;
					goto m1;
				}
			}
		}
	}
m1: ;
	if(mark)
	{
		p = n+1;
		while(pre[p]!=-1)
		{
			if(F[p] < C)
				C = F[p];
			p = pre[p];
		}
		ans += C;
		p = n+1;
		while(pre[p]!=-1)
		{
			for(i = 0; i < graph[p].size(); i++)
				if(graph[p][i].id == pre[p])
				{
					graph[p][i].c += C;
					break;
				}
			for(i = 0; i < graph[pre[p]].size(); i++)
				if(graph[pre[p]][i].id == p)
				{
					graph[pre[p]][i].c -= C;
					break;
				}
			p = pre[p];
		}
	}
	return mark;
}

int main()
{
	edge t;
	int i;
	int a, b, c;

	scanf("%d%d",&n,&m);
	ans = 0;
	for(i = 1; i <= n; i++)
	{
		scanf("%d%d",&a,&b);
		if (a == b)
		{
			ans += a;
			continue;
		}
		if (a < b)
		{
			ans += a;
			t.c = b-a;
			t.id = n+1;
			graph[i].push_back(t);
		}
		else
		{
			ans += b;
			t.c = a-b;
			t.id = i;
			graph[0].push_back(t);
		}
	}
	for(i = 1; i <= m; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		t.c = c;
		t.id = a;
		graph[b].push_back(t);
		t.id = b;
		graph[a].push_back(t);
	}
	while(bfs());
	printf("%d\n",ans);
	return 0;
}