3168759_ac_511ms_844k.cc

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

#include <stdio.h>
#include <string.h>

struct node
{
	int u, v, w;
}edge[40001];

int map[201][201];
int N, P, T;
int min, mid, max;
int ans, C;

void input()
{
	int i;

	min = 2100000000;
	max = 0;
	scanf("%d%d%d",&N,&P,&T);
	for(i = 0; i < P; i++)
	{
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
		edge[i].u--;
		edge[i].v--;
		if(edge[i].w > max)
		{
			max = edge[i].w;
		}
		if(edge[i].w < min)
		{
			min = edge[i].w;
		}
	}
}

void getgraph()
{
	int i;

	memset(map,0,sizeof(map));
	for(i = 0; i < P; i++)
	{
		map[edge[i].u][edge[i].v] += (edge[i].w <= mid);
		map[edge[i].v][edge[i].u] = map[edge[i].u][edge[i].v];
	}
}

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

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = 2100000000;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < N; i++)
			if(map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = map[p][i];
				if(i==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];
		}
		p = N-1;
		while(pre[p]!=-1)
		{
			map[pre[p]][p] -= C;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

void solve()
{
	while(min < max)
	{
		mid = (max+min)>>1;
		getgraph();
		ans = 0;
		while(ans<T&&bfs());
		if(ans < T)
			min = mid+1;
		else
			max = mid;
	}
	printf("%d\n",min);
}

int main()
{
	input();
	solve();
	return 0;
}