锐客网

  1. 首页 > it技术 > >

online|hdu1816Get Luffy Out *

图论其他HDU二分online2-SATjudge

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1816
题意：有2*n种钥匙，n对钥匙的约束（用了一把另一把那种钥匙就不能用了），m扇门。每扇门上有两把锁，打开一把就能打开门。问最多能打开多少扇门。
分析：求最大值我们可以二分，然后根据约束条件用2-SAT算法就行了。
代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef double db; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; const db eps=1e-5; const int N=4e3+50; const int M=7e3+10; const ll MOD=1000000007; const int mod=1000000007; const int MAX=1000000010; const double pi=acos(-1.0); struct twosat { int n,k,d[N]; bool mark[N]; int tot,u[N],v[M],pre[M]; void init(int a) { n=a<<1; tot=0; for (int i=0; i>1; while (l+1>1; else r=mid,mid=(l+r)>>1; printf("%d\n", l); } return 0; }



    推荐阅读


    上一篇：online|hdu3622Bomb Game

    下一篇：online|hdu5955Guessing the Dice Roll