欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

HDU 1816, POJ 2723 Get Luffy Out(2

程序员文章站 2022-05-07 17:45:53
...

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 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXNODE = 2105;

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

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