POJ 2724 Purifying Machine 题解 《挑战程序设计竞赛》

POJ 2724 Purifying Machine

食品安全：工作太累，码农Mike决定转行卖煎饼。城管说Mike的煎饼不卫生，于是Mike买了台消毒器。消毒器有N个二进制开关，可以批量消毒对应数字id的煎饼。如果开关置为*表示这一位同时匹配0和1。有天消毒器本身进了地沟油，导致M个操作涉及的煎饼全部中毒。Mike清洗消毒器后，决定尽快把煎饼再次消毒，求最小操作次数？

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

二分图匹配 

由于*同时消毒2次，所以应当尽量使用*。将所有操作中的*转码为0和1后，得到一个比特向量集合S。S中如果两个比特向量只有一位不同，则连一条边，构成二分图。二分图的最大独立集即为所求，因为独立集中任意两个操作都无法使用*合并。

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

#define MAX_N 10 + 16
#define MAX_M 2000 + 16

////////////////////////最大流开始//////////////////////////////////////
#define MAX_V MAX_M * 2
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();
	}
}
///////////////////////////////最大流结束/////////////////////////////////////
vector<int> operations;
char buffer[MAX_N];
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, M;
	while (scanf("%d %d", &N, &M) != EOF && N && M)
	{
		operations.clear();
		for (int _ = 0; _ < M; ++_)
		{
			scanf(" %s ", buffer);
			int t = 0;
			for (int i = 0; i < N; ++i) 
			{
				if (buffer[i] == '1') 
				{
					t += 1 << (N - i - 1);
				}
			}
			operations.push_back(t);
			for (int i = 0; i < N; ++i) 
			{
				if (buffer[i] == '*') 
				{
					t += 1 << (N - i - 1);
				}
			}
			operations.push_back(t);
		}
		sort(operations.begin(), operations.end());
		operations.erase(unique(operations.begin(), operations.end()), operations.end());
		V = operations.size();
		clear();
		for (int i = 0; i < V; ++i)
		{
			for (int j = i + 1; j < V; ++j)
			{
				bitset<32> diff = operations[i] ^ operations[j];
				if (diff.count() == 1)
				{
					add_edge(i, j);
				}
			}
		}
		printf("%d\n", V - bipartite_matching());
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

上面的bitset逼格不够高，可以如下装逼：

int diff = operations[i] ^ operations[j];
if ((diff & (-diff)) == diff)
{
    add_edge(i, j);
}

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