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
上一篇: Oracle中nvl()函数
下一篇: MySQL主从同步故障