4032453_ac_454ms_5916k.cpp

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

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

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

int N, M;
int tm[50][50];

void init()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			scanf("%d", &tm[i][j]);
		}
	}
}

int que[1000000];
int v[3000], fa[3000];
vector <node> graph[3000];

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;

	for (i = 0; i < 3000; i++)
	{
		graph[i].clear();
	}
	for (i = 1; i <= N; i++)
	{
		t.id = i;
		t.c = 1;
		t.f = t.w = 0;
		graph[0].push_back(t);
	}
	for (i = N + 1; i <= N + M * N; i++)
	{
		t.id = N + 1 + M * N;
		t.c = 1;
		t.f = t.w = 0;
		graph[i].push_back(t);
	}
	for(i = 1; i <= N; i++)
	{
		st = N + 1;
		for (j = 1; j <= M; j++)
		{
			for (k = 1; k <= N; k++)
			{
				t.id = st;
				t.c = 1;
				t.w = k * tm[i - 1][j - 1];
				t.f = 0;
				graph[i].push_back(t);
				t.id = i;
				t.c = t.f = 0;
				t.w = -k * tm[i - 1][j - 1];
				graph[st].push_back(t);
				st++;
			}
		}
	}
	minc = 0;
	st = 0;
	ed = N + 1 + M * N;
	n = ed + 1;
}

int main()
{
	int cas;

	scanf("%d", &cas);
	while (cas--)
	{
		init();
		get_graph();
		minc = 0;
		while(find_way())
			add_way();
		printf("%.6lf\n",1.0 * minc / N);
	}
	return 0;
}