HDU 1816， POJ 2723 Get Luffy Out（2

HDU 1816， POJ 2723 Get Luffy Out 题目链接 题意：N串钥匙，每串2把，只能选一把，然后有n个大门，每个门有两个锁，开了一个就能通过，问选一些钥匙，最多能通过多少个门 思路：二分通过个数，然后对于钥匙建边至少一个不选，门建边至少一个选，然后2-sat

HDU 1816， POJ 2723 Get Luffy Out

题目链接

题意：N串钥匙，每串2把，只能选一把，然后有n个大门，每个门有两个锁，开了一个就能通过，问选一些钥匙，最多能通过多少个门

思路：二分通过个数，然后对于钥匙建边至少一个不选，门建边至少一个选，然后2-sat搞一下即可。
一开始是按每串钥匙为1个结点，可是后面发现数据有可能一把钥匙，出现在不同串（真是不合理），所以这个做法就跪了

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXNODE = 2105;

struct TwoSet {
	int n;
	vector<int> g[MAXNODE * 2];
	bool mark[MAXNODE * 2];
	int S[MAXNODE * 2], sn;

	void init(int tot) {
		n = tot * 2;
		for (int i = 0; i <br>
<br>



</int></algorithm></vector></cstdlib></cstring></cstdio>