2723 Get Luffy Out

問題概要

m枚の扉を順に、なるべく多くの枚数を開けたい。
扉には二つの錠があり、どちらかの錠を開ければ扉は開く。

錠は2*n種類あり、全ての錠にはただ一つの異なる錠が対応している。
錠の鍵を一度使用すると、対応する錠の鍵は消滅して使用不可能になる。

錠の対応関係および、各扉についている錠の番号が与えられるとき、
開けられる扉の最大の枚数を求めよ。

n≦1024,m≦2048を満たす。

解法

k番目までの扉を開けられるかについて考える。
対になっている鍵はどちらか一方しかつかえず、かつk番目までの全ての扉を開けなければならない。これは良く見ると2-SAT問題である。

2-SATは線形時間で解けるので、あとはkを動かして二分探索すればよい。

2-SATの問題解いたの初めてのような気がする……
上位の人の実行速度は1000倍くらい速いので、もしかしたら二分探索要らないのかも？

ソースコード

int n,m,p[3000],ky[3000];

int main(){
	while(scanf("%d%d",&n,&m),n){
	vector<clause> cs;
		rep(i,n){
			int a,b; scanf("%d%d",&a,&b);
			p[a]=VAR(i); p[b]=NOT(VAR(i));
		}
		rep(i,m){
			int a,b; scanf("%d%d",&a,&b);
			cs.pb(mp(p[a],p[b]));
		}
		int lo=1,hi=m+1,mid;
		while(lo+1<hi){
			mid=(lo+hi)/2;
			if(two_satisfiability(mid,n,cs))lo=mid; else hi=mid;
		}
		printf("%d\n",lo);
	}
	return 0;
}