[POJ3683]Priest John's Busiest Day

vjudge

题意

有(n)对新人在同一天结婚。(John)作为小镇上唯一的神父（牧师？）需要去给每一场婚礼搞一个仪式。第(i)场婚礼的持续时间是(S_i)到(T_i)，仪式可以安排在婚礼的前(D_i)分钟也可以安排在后(D_i)分钟举办。已知(John)可以从一个婚礼现场瞬移到另一个婚礼现场，求给他安排一个合法方案使其可以参加主持所有婚礼的仪式，或判断无解。
（手写翻译233）
(nle1000)

sol

每场婚礼只有两个状态，由此想到(2-sat)。
枚举两场婚礼，把相冲突的连边。具体而言，假设(u)和(v)两个变量存在冲突，就连边(u->v',v->u')。总边数是(O(n^2))级别的。
然后(Tarjan)强连通分量缩点，先判无解。
输出一组合法方案？
直接选(i)和(i')中所在强连通分量标号较小的就可以了。

code

#include<cstdio>
#include<algorithm>
using namespace std;
int gi()
{
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 2e3+5;
int n,s[N],t[N],d[N],to[N*N],nxt[N*N],head[N],cnt;
int dfn[N],low[N],tim,Stack[N],top,vis[N],bel[N],scc;
int GetTime()
{
	return gi()*60+gi();
}
void OutputTime(int x,char ch)
{
	printf("%.2d:%.2d%c",x/60,x%60,ch);
}
bool Cross(int l1,int r1,int l2,int r2)
{
	if (l1>l2) swap(l1,l2),swap(r1,r2);
	return l2<r1;
}
void link(int u,int v)
{
	to[++cnt]=v;nxt[cnt]=head[u];
	head[u]=cnt;
}
void Tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	Stack[++top]=u;vis[u]=1;
	for (int e=head[u];e;e=nxt[e])
		if (!dfn[to[e]]) Tarjan(to[e]),low[u]=min(low[u],low[to[e]]);
		else if (vis[to[e]]) low[u]=min(low[u],dfn[to[e]]);
	if (dfn[u]==low[u])
	{
		++scc;int v;
		do{
			v=Stack[top--];
			vis[v]=0;bel[v]=scc;
		}while (u!=v);
	}
}
int main()
{
	n=gi();
	for (int i=1;i<=n;++i) s[i]=GetTime(),t[i]=GetTime(),d[i]=gi();
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
		{
			if (Cross(s[i],s[i]+d[i],s[j],s[j]+d[j]))
				link(i,j+n),link(j,i+n);
			if (Cross(s[i],s[i]+d[i],t[j]-d[j],t[j]))
				link(i,j),link(j+n,i+n);
			if (Cross(t[i]-d[i],t[i],s[j],s[j]+d[j]))
				link(i+n,j+n),link(j,i);
			if (Cross(t[i]-d[i],t[i],t[j]-d[j],t[j]))
				link(i+n,j),link(j+n,i);
		}
	for (int i=1;i<=2*n;++i) if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=n;++i) if (bel[i]==bel[i+n]) return puts("NO"),0;
	puts("YES");
	for (int i=1;i<=n;++i)
		if (bel[i]<bel[i+n])
			OutputTime(s[i],' '),OutputTime(s[i]+d[i],'
');
		else
			OutputTime(t[i]-d[i],' '),OutputTime(t[i],'
');
	return 0;
}