2890830_ac_374ms_2036k.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 que[1000000];
int v[5010], fa[5010];
vector <node> graph[5010];

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];
}

int main()
{
	int i, j, id, ID, num;
	node t;

	scanf("%d%d",&n,&k);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			scanf("%d",&num);
			id = i*n+j;
			id = id*2+1;
			t.id = id+1;
			t.c = 1;
			t.f = 0;t.w = -num;
			graph[id].push_back(t);
			t.w = num;t.c = 0;
			t.id = id;
			graph[id+1].push_back(t);
		}
	}
	t.id = 1;t.c = k;t.f = t.w = 0;
	graph[0].push_back(t);
	t.c = 0;t.id = 0;
	graph[1].push_back(t);
	id = n*n*2;
	t.id = id;
	graph[id+1].push_back(t);
	t.id = id+1;t.c = k;
	graph[id].push_back(t);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(i!=n-1)
			{
				id = (i*n+j)*2+1;ID = ((i+1)*n+j)*2+1;
				t.c = inf;t.f = t.w = 0;
				t.id = ID;
				graph[id].push_back(t);
				graph[id+1].push_back(t);
				t.id = ID+1;
				graph[id].push_back(t);
				graph[id+1].push_back(t);
				t.c = 0;
				t.id = id;
				graph[ID].push_back(t);
				graph[ID+1].push_back(t);
				t.id = id+1;
				graph[ID].push_back(t);
				graph[ID+1].push_back(t);
			}
			if(j!=n-1)
			{
				id = (i*n+j)*2+1;ID = id+2;
				t.c = inf;t.f = t.w = 0;
				t.id = ID;
				graph[id].push_back(t);
				graph[id+1].push_back(t);
				t.id = ID+1;
				graph[id].push_back(t);
				graph[id+1].push_back(t);
				t.c = 0;
				t.id = id;
				graph[ID].push_back(t);
				graph[ID+1].push_back(t);
				t.id = id+1;
				graph[ID].push_back(t);
				graph[ID+1].push_back(t);
			}
		}
	}
	n = n*n*2+2;
	st = 0;ed = n-1;
	minc = 0;
	while(find_way())
		add_way();
	printf("%d\n",-minc);
	return 0;
}