3301364_ac_782ms_4612k.cc

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

#include <stdio.h>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define maxn 410
#define inf 100000000

using namespace std;

typedef __int64 Int;

int n, m;
int map[maxn*2][maxn*2];
int now[maxn], cap[maxn];
Int cost[maxn][maxn];
int maxflow, tot;
vector <Int> tv, v;

void floyd()
{
	int i, j, k;
 
	for(k = 1; k <= n; k++)
	{
		for(i = 1; i <= n; i++)
		{
			if(cost[i][k]!=-1)
			{
				for(j = 1; j <= n; j++)
				{
					if(cost[k][j]==-1)
					{
						continue;
					}
					if(cost[i][j]==-1||cost[i][k]+cost[k][j]<cost[i][j])
					{
						cost[i][j]=cost[i][k]+cost[k][j]; 
					}
				}
			}
		}  
	}
	v.clear();
	v.push_back(0);
	for(i = 1; i <= n; i++)
	{
		for(j = i+1; j <= n; j++)
		{
			if(cost[i][j]!=-1)
			{
				v.push_back(cost[i][j]);
			}
		}
	}
	tv.clear();
	sort(v.begin(),v.end());
	for(i = 0; i < v.size(); i++)
	{
		tv.push_back(v[i]);
		j = i;
		while(j<v.size()&&v[j]==v[i])
			j++;
		i = j-1;
	}
}

void getgraph(Int maxtime)
{
	int i, j;

	memset(map,0,sizeof(map));
	for(i = 1; i <= n; i++)
	{
		map[0][i] = now[i];
		map[i+n][2*n+1] = cap[i];
	}
	for(i = 1; i <= n; i++)
	{
		map[i][i+n] = inf;
		for(j = i+1; j <= n; j++)
		{
			if(cost[i][j]!=-1&&cost[i][j] <= maxtime)
			{
				map[i][j+n] = map[j][i+n] = inf;
			}
		}
	}
}

int bfs()
{
	int i, mark = 0;
	int f, r, p;
	int pre[maxn*2], visited[maxn*2];
	int queue[maxn*2];
	int C, F[maxn*2];

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = inf;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < m; i++)
			if(map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = map[p][i];
				if(i==m-1)
				{	
					mark = 1;
					goto m1;
				}
			}
	}
	m1:;
	if(mark)
	{
		p = m-1;
		while(pre[p]!=-1)
		{
			if(F[p]<C)
				C = F[p];
			p = pre[p];
		}
		p = m-1;
		while(pre[p]!=-1)
		{
			map[pre[p]][p] -= C;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		maxflow += C;
	}
	return mark;
}

int check()
{
	maxflow = 0;
	while(bfs());
	return maxflow==tot;
}

int main()
{
	int i;
	int a, b;
	Int w, mintime;
	int min, mid, max;

	scanf("%d%d",&n,&m);
	tot = 0;
	for(i = 1; i <= n; i++)
	{
		scanf("%d%d",&now[i],&cap[i]);
		tot += now[i];
	}
	memset(cost,-1,sizeof(cost));
	for(i = 1; i <= m; i++)
	{
		scanf("%d%d%I64d",&a,&b,&w);
		if(a==b)
		{
			continue;
		}
		if(cost[a][b]==-1||w < cost[a][b])
		{
			cost[a][b] = cost[b][a] = w;
		}
	}
	floyd();
	mintime = -1;
	m = 2*n+2;
	min = 0;max = tv.size()-1;
	while(min <= max)
	{
		mid = (min+max)/2;
		getgraph(tv[mid]);
		if(check())
		{
			mintime = tv[mid];
			if(max==mid)
				break;
			max = mid;
		}
		else
			min = mid+1;
	}
	printf("%I64d\n",mintime);
	return 0;
}