放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

POJ 3692 Kindergarten​ 题解 《挑战程序设计竞赛》

目录

POJ 3692 Kindergarten

贵圈真乱:有G个绿孩子和B个蓝孩子,都是同性恋,另有M对异性恋。求最大集合,集合内每个孩子都彼此有一腿。

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

二分图匹配

我的翻译越来越和谐了,两个完全子图组成原图,其补图一定是二分图。二分图的最大独立集即为所求,因为独立集两两之间没有边,代表两两彼此有关系。

参照《POJ 1466 Girls and Boys》的做法即可:

#include <iostream>
using namespace std;

#include <iostream>
#include <vector>
using namespace std;

////////////////////////最大流开始//////////////////////////////////////
#define MAX_V 200 * 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();
	}
}
///////////////////////////////最大流结束/////////////////////////////////////

bool graph[MAX_V][MAX_V];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int G, B, M, id = 0;
	while (scanf("%d%d%d", &G, &B, &M) != EOF && G)
	{
		V = G + B;
		memset(graph, 0, sizeof(graph));
		clear();
		for (int i = 0; i < M; ++i)
		{
			int X, Y;
			scanf("%d%d", &X, &Y);
			--X; --Y;
			graph[X][Y] = true;
		}
		for (int i = 0; i < G; ++i)
		{
			for (int j = 0; j < B; ++j)
			{
				if (!graph[i][j])
				{
					add_edge(i, j + G);
				}
			}
		}
		printf("Case %d: %d\n", ++id, V - bipartite_matching());
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
13808254 hankcs 3692 Accepted 576K 110MS C++ 2024B 2015-01-23 22:00:19

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3692 Kindergarten​ 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机