POJ 3683 Priest Phon's Busiest Day

蟻本復習中。

問題

N組のカップルが同じ日に結婚式を挙げる。
i番目の結婚式は時刻s[i]からt[i]の間に開かれ、その最初か最後のどちらかのd[i]分間特別な式典を行う必要がある。
（s[i]〜s[i]+d[i]かt[i]-d[i]〜t[i]のどちらか）

式典には司祭の出席が必要で、司祭は同時に二つ以上の式典に出ることはできない。
ただし、司祭の移動時間は無視でき、終了時間と開始時間の等しい2つの式典に出席することもできる。

司祭が全ての式典に出席できるかを判定せよ。
可能なら、どの時間帯の式典に出席するか、可能な答え一つを出力せよ。

制約条件

N≦1000

方針

蟻本の解説の通り。
結婚式iの、前のほうの式典に出席することをxi、後ろに出席することを¬xiとする。
式典i,jがバッティングしている場合、¬(xi∧xj)が成り立つ必要があるが、これは= (¬xi∨¬xj)と変形できるため、2-SAT問題に帰着できる。

ソースコード

蟻本の実装はもう少し綺麗に書ける。
こんな感じ。

int n,s[2000],d[2000];

int main(){
	int n; scanf("%d",&n);
	rep(i,n){
		int a,b,x,y;
		scanf("%d:%d %d:%d %d",&a,&b,&x,&y,d+i);
		s[i]=a*60+b;
		s[i+n]=x*60+y-d[i];
		d[i+n]=d[i];
	}
	V=2*n;
	rep(i,2*n)rep(j,i){
		if(!(s[j]+d[j]<=s[i]||s[i]+d[i]<=s[j])){
			#define NOT(x) (x<n?x+n:x-n)
			add_edge(i,NOT(j));
			add_edge(j,NOT(i));
		}
	}
	scc();
	
	rep(i,n){
		if(cmp[i]==cmp[i+n]){
			printf("NO\n");
			return 0;
		}
	}
	
	printf("YES\n");
	rep(i,n){
		if(cmp[i]>cmp[i+n])printf("%02d:%02d %02d:%02d\n",s[i]/60,s[i]%60,(s[i]+d[i])/60,(s[i]+d[i])%60);
		else printf("%02d:%02d %02d:%02d\n",s[i+n]/60,s[i+n]%60,(s[i+n]+d[i])/60,(s[i+n]+d[i])%60);
	}
	return 0;
}