4083167_ac_0ms_332k.cc

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

#include <stdio.h>
#include <vector>
#define inf 10000000
using namespace std;

int n, m, minc;
int st, ed;
struct node
{
	int id;
	int c, f, w;
};

int que[100], cnt;
int v[100], fa[100];
vector <node> graph[100];

bool init()
{
	scanf("%d%d", &n, &m);
	return !(n == 0 && m == 0);
}

bool find_way()
{
	int id;
	int i, s;
	int f, r;

	for(i = 0; i < n; i++)
		v[i] = inf;
	v[st] = 0;
	f = r = -1;
	que[++r] = st;
	while(f!=r)
	{
		++f;
		s = que[f];
		for(i = 0; i < graph[s].size(); i++)
		{
			id = graph[s][i].id;
			if(graph[s][i].f<graph[s][i].c&&v[s]+graph[s][i].w<v[id])
			{
				v[id] = v[s]+graph[s][i].w;
				que[++r] = id;
				fa[id] = s;
			}
		}
	}
	if(v[ed] < inf)
		return true;
	return false;
}

void add_way()
{
	int i, j, l, tmp;

	i = ed;
	do
	{
		j = i;
		i = fa[j];
		for(l = 0; l < graph[i].size(); l++)
		{
			if(graph[i][l].id == j)
			{
				graph[i][l].f++;
				tmp = -graph[i][l].f;
				break;
			}
		}
		for(l = 0; l < graph[j].size(); l++)
		{
			if(graph[j][l].id == i)
			{
				graph[j][l].f = tmp;
				break;
			}
		}
	}while(i!=st);
	minc += v[ed];
}

void get_graph()
{
	int i, j, k, st;
	node t;
	int u, v, cost;

	cnt = 0;
	for (i = 0; i < 100; i++)
	{
		graph[i].clear();
	}
	for (i = 0; i < n; i++)
	{
		t.id = i + n;
		t.c = (i == 0 || i == n - 1) ? inf : 1;
		t.f = 0;
		t.w = 0;
		graph[i].push_back(t);
		t.c = 0;
		t.id = i;
		graph[i + n].push_back(t);
	}
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &u, &v, &cost);
		t.id = v;
		t.c = 1;
		t.f = 0;
		t.w = cost;
		graph[u + n].push_back(t);
		t.w = -cost;
		t.c = 0;
		t.id = u + n;
		graph[v].push_back(t);
	}
	minc = 0;
	n = n << 1;
	st = 0;
	ed = n - 1;
}

int main()
{
	int now (1);

	while (init())
	{
		printf("Instance #%d: ", now++);
		get_graph();
		minc = 0;
		while(cnt < 2 && find_way())
		{
			cnt++;
			add_way();
		}
		if (cnt < 2)
		{
			puts("Not possible");
			continue;
		}
		printf("%d\n", minc);
	}
	return 0;
}