2954678_tle.cc

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

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

using namespace std;

int n, m, ans;
int S, T;
int L, R;
int d[MaxV], op[MaxV], st[MaxV], lst[MaxV];
int tp;

struct edge
{
	int id;
	int c;
};

vector <edge> graph[MaxV];

int calc()
{
	int t, i;

	memset(d,0,sizeof(d));
	d[op[0] = S] = 1;
	st[1] = 1;
	for(L = 0,R = 1; L < R; L++)
	{
		t = op[L];
		for(i = 0; i < graph[t].size(); i++)
		{
			if(graph[t][i].c&&!d[graph[t][i].id])
			{
				d[op[R++] = graph[t][i].id] = d[op[L]] + 1;
				st[graph[t][i].id] = R;
			}
		}
	}
	return d[T];
}

int refresh(int &tp)
{
	int i, j, t, ret, top;

	top = tp;
	ret = Inf;
	for(i = top-1; i; i--)
	{
		t = lst[i-1];
		for(j = 0; j < graph[t].size(); j++)
			if(graph[t][j].id==lst[i])
			{
				if(graph[t][j].c<ret)
					ret = graph[t][j].c;
				break;
			}
	}
	for(i = top-1; i; i--)
	{
		t = lst[i];
		for(j = 0; j < graph[t].size(); j++)
			if(graph[t][j].id==lst[i-1])
			{
				graph[t][j].c += ret;
				break;
			}
		t = lst[i-1];
		for(j = 0; j < graph[t].size(); j++)
			if(graph[t][j].id==lst[i])
			{
				graph[t][j].c -= ret;
				if(graph[t][j].c == 0)
					tp = i - 1;
				break;
			}
	}
	return ret;
}

int fnext(int u)
{
	int i, t;

	if(d[u]==d[op[R-1]])
		return -1;
	for(i = 0; i < graph[u].size(); i++)
	{
		t = graph[u][i].id;
		if(d[t]>0&&d[u]!=d[t])
			return t;
	}
	return -1;
}

void flow()
{
	for(tp = 1, lst[0] = S; tp; )
	{
		if(lst[tp-1] == T)
		{
			ans += refresh(tp);
		}
		else
		{
			lst[tp] = fnext(lst[tp-1]);
			if(lst[tp]>=0)
				tp++;
			else
				d[lst[--tp]] = -10;

		}
	}
}

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);
			t.id = i;
			graph[n+1].push_back(t);
		}
		else
		{
			ans += b;
			t.c = a-b;
			t.id = i;
			graph[0].push_back(t);
			t.id = 0;
			graph[i].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);
	}
	S = 0; T = n+1;
	while(calc())
		flow();
	printf("%d\n",ans);
	return 0;
}