3772615_tle.cpp

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

#include <stdio.h>
#include <set>
#include <string.h>
#include <algorithm>
#define INF 2100000000

using namespace std;

struct node
{
	int c, w, f;
}net[410][410];

struct Node
{
	int v, fa;
}best[410];

int n, s, t;
int minc;
set <int> num;
int N, K;

struct NODE
{
	int a, b, w;
}itv[201];

int ID[100001];

void init()
{
	int i;

	scanf("%d%d", &N, &K);
	memset(net, 0, sizeof(net));
	num.clear();
	for (i = 0; i < N; i++)
	{
		scanf("%d%d%d", &itv[i].a, &itv[i].b, &itv[i].w);
		num.insert(itv[i].a);
		num.insert(itv[i].b);
	}
	int id = 1;
	for (set<int> ::iterator it = num.begin(); it != num.end(); ++it, ++id)
	{
		ID[*it] = id;
	}
	for (i = 0; i <= id; i++)
	{
		net[i][i+1].c = K;
		net[i][i+1].w = 0;
	}
	for (i = 0; i < N; i++)
	{
		net[ID[itv[i].a]][ID[itv[i].b]].c = 1;
		net[ID[itv[i].a]][ID[itv[i].b]].w = -itv[i].w;
		net[ID[itv[i].b]][ID[itv[i].a]].w = itv[i].w;
	}
	minc = 0;
	n = id + 2;
	s = 0;
	t = n - 1;
}

int Find_Way()
{
	int i, j;
	int quit;

	for(i = 0; i < n; i++)
		best[i].v = INF;
	best[s].v = 0;
	do
	{
		quit = 1;
		for(i = 0; i < n; i++)
		{
			if(best[i].v<INF)
			{
				for(j = 0; j < n; j++)
				{
					if(net[i][j].f<net[i][j].c&&best[i].v+net[i][j].w<best[j].v)
					{
						best[j].v = best[i].v+net[i][j].w;
						best[j].fa = i;
						quit = 0;
					}
				}
			}
		}
	}while(!quit);
	if(best[t].v<INF)
		return 1;
	return 0;
}

void Add_Way()
{
	int i, j;
	int MINC = 1;

	i = t;
	do
	{
		j = i;
		i = best[j].fa;
		net[i][j].f += MINC;
		net[j][i].f = -net[i][j].f;
	}
	while(i!=s);
	minc += best[t].v;
}

int main()
{
	int cas;

	scanf("%d", &cas);
	while(cas-- != 0)
	{
		init();
		while(Find_Way())
			Add_Way();
		printf("%d\n", -minc);
	}
	return 0;
}