AOJ 2251 Merry Christmas 题解 《挑战程序设计竞赛》

AOJ 2251 Merry Christmas

国际圣诞礼品公司：International Christmas Present Company (ICPC)是一家圣诞礼品快递公司，由M条路连起的N户人家发起了L次订单，分别要求在时刻t准时将礼物送到p处。求最少需要几个圣诞老人？

3.5借助水流解决问题的网络流 

二分图匹配 

不妨考虑最坏情况，L个订单分配给L个圣诞老人。再考虑如何省下人力，假设处理完订单Q_i，还有时间步行到Q_j指定的地址，那么这两个订单可以交给同一个人处理。于是建立二分图，可以合并的订单之间连一条边，最小边覆盖即为所求。

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

////////////////////////最大流开始//////////////////////////////////////
#define MAX_V 1000 * 2 + 16
int V;                 // 顶点数
vector<int> G[MAX_V];    // 图的邻接表
int match[MAX_V];      // 所匹配的顶点
bool used[MAX_V];      // DFS中用到的访问标记

// 向图中增加一条连接u和v的边
void add_edge(int u, int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
}

// 通过DFS寻找增广路
bool dfs(int v)
{
	used[v] = true;
	for (vector<int>::iterator it = G[v].begin(); it != G[v].end(); ++it)
	{
		int u = *it, w = match[u];
		if (w < 0 || !used[w] && dfs(w))
		{
			match[v] = u;
			match[u] = v;
			return true;
		}
	}

	return false;
}

// 求解二分图的最大匹配
int bipartite_matching()
{
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; ++v)
	{
		if (match[v] < 0)
		{
			memset(used, 0, sizeof(used));
			if (dfs(v))
			{
				++res;
			}
		}
	}

	return res;
}

void clear()
{
	for (int i = 0; i < V; ++i)
	{
		G[i].clear();
	}
}

///////////////////////////////最大流结束/////////////////////////////////////
#define  MAX_N 100
#define  MAX_L 1000
#define  INF 0x3f3f3f3f

int distance_matrix[MAX_N][MAX_N];		// 两点间最短路
int p[MAX_L], t[MAX_L];					// 房间编号，时刻

bool update_min(int& v, const int& t)
{
	if (t < v)
	{
		v = t;
		return true;
	}
	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	int N, M, L;
	while (scanf("%d%d%d", &N, &M, &L) != EOF && N)
	{
		V = L * 2;
		clear();
		memset(distance_matrix, INF, sizeof(distance_matrix));

		for (int _ = 0; _ < M; ++_)
		{
			int u, v, d;
			scanf("%d%d%d", &u, &v, &d);
			distance_matrix[u][v] = distance_matrix[v][u] = d;
		}

		for (int i = 0; i < L; ++i)
		{
			scanf("%d%d", p + i, t + i);
		}

		// warshall_floyd 两点间最短路
		for (int k = 0; k < N; ++k) 
		{
			distance_matrix[k][k] = 0;
			for (int i = 0; i < N; ++i) 
			{
				for (int j = 0; j < N; ++j) 
				{
					update_min(distance_matrix[i][j], distance_matrix[i][k] + distance_matrix[k][j]);
				}
			}
		}

		for (int i = 0; i < L; ++i) 
		{
			for (int j = 0; j < L; ++j)  
			{
				if (i != j && t[i] + distance_matrix[p[i]][p[j]] <= t[j])
				{
					add_edge(2 * i, 2 * j + 1);	// 可以在i之后处理j，连一条边
				}
			}
		}

		printf("%d\n", L - bipartite_matching());
	}
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2251 Merry Christmas 题解 《挑战程序设计竞赛》