先象征性地描述一下问题：一组（或者一个）东西有且仅有两种选择，要么选这个，要么选那个，还有一堆的约束条件
图论问题，当然是建边跑图喽
给出模型：
模型一：两者（A，B）不能同时取 那么选择了A就只能选择B’，选择了B就只能选择A’
连边A→B’，B→A’ 模型二：两者（A，B）不能同时不取 那么选择了A’就只能选择B，选择了B’就只能选择A
连边A’→B，B’→A 模型三：两者（A，B）要么都取，要么都不取 那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’
连边A→B，B→A，A’→B’，B’→A’ 模型四：两者（A，A’）必取A 那么，那么，该怎么说呢？先说连边吧。
连边A’→A
题目POJ3683
然后说一下这个题的意思：
如果某两个婚礼进行仪式的时间有重合
那么就存在了矛盾关系,通过这些关系连边
Tarjan缩点重新建图（这里建反向图）,判断
将一个未着色点 x 上色同时，把与它矛盾的点 y 以及 y 的所有子孙节点上另外一种颜色
上色完成后，进行拓扑排序，选择一种颜色的点输出就是一组可行解
介绍一下实现：
int n,cnt,scc,ind,top;
int a[maxn],b[maxn],belong[maxn],op[maxn];
bool inq[maxn];int dfn[maxn],low[maxn],q[maxn],col[maxn];
int g[maxn],gd[maxn],d[maxn];
struct Edge{int t,next;}e[maxm],ed[maxm];
ind是自增的用来记录dfn，scc是连通分量个数
belong用于存每一个点属于哪一个连通分量
然后op用来记录同一组的互斥条件
col用来存颜色
d用来存点的度数，便于拓扑排序
下面给出完整实现，感觉这个题可以很好地拆成几个很好地模板（就比如说拓扑排序，重新建图，强连通缩点，哈哈）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
int n,cnt,scc,ind,top;
int a[maxn],b[maxn],belong[maxn],op[maxn];
bool inq[maxn];int dfn[maxn],low[maxn],q[maxn],col[maxn];
int g[maxn],gd[maxn],d[maxn];
struct Edge{int t,next;}e[maxm],ed[maxm];
void addedge(int u,int v)
{
e[++cnt].t=v;e[cnt].next=g[u];
g[u]=cnt;
}
void addedge2(int u,int v)
{
d[v]++;
ed[++cnt].t=v;ed[cnt].next=gd[u];
gd[u]=cnt;
}
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>'') {if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//a[2i]-b[2i]前半程
//a[2i-1]-b[2i-1]后半程
bool jud(int x,int y)
{
if(b[x]<=a[y]||a[x]>=b[y]) return ;
return ;
}
void build()
{
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
if(jud(*i,*j))
{
addedge(*i,*j-);
addedge(*j,*i-);
}
if(jud(*i,*j-))
{
addedge(*i,*j);
addedge(*j-,*i-);
}
if(jud(*i-,*j))
{
addedge(*i-,*j-);
addedge(*j,*i);
}
if(jud(*i-,*j-))
{
addedge(*i-,*j);
addedge(*j-,*i);
}
}
}
void tarjan(int x)
{
//cout<<x<<endl;
dfn[x]=low[x]=++ind;
q[++top]=x;inq[x]=;
for(int tmp=g[x];tmp;tmp=e[tmp].next)
if(!dfn[e[tmp].t])
{
tarjan(e[tmp].t);
low[x]=min(low[e[tmp].t],low[x]);
}
else if(inq[e[tmp].t])
low[x]=min(dfn[e[tmp].t],low[x]);
if(low[x]==dfn[x])
{
int temp=;scc++;
while(temp!=x)
{
temp=q[top--];
inq[temp]=;
belong[temp]=scc;
}
}
}
void rebuild()
{
cnt=;
for(int x=;x<=*n;x++)
for(int tmp=g[x];tmp;tmp=e[tmp].next)
if(belong[x]!=belong[e[tmp].t])
{
//cout<<belong[e[tmp].t]<<" "<<belong[x]<<endl;
addedge2(belong[e[tmp].t],belong[x]);
} }
void dfs(int x)
{
if(col[x]) return;
col[x]=-;
for(int tmp=gd[x];tmp;tmp=ed[tmp].next)
dfs(ed[tmp].t);
}
void topsort()
{
for(int i=;i<=scc;i++)
if(!d[i]) q[++top]=i;
while(top)
{
int temp=q[top--];
//cout<<temp<<endl;
if(col[temp]) continue;
col[temp]=;dfs(op[temp]);
for(int tmp=gd[temp];tmp;tmp=ed[tmp].next)
{
d[ed[tmp].t]--;
if(!d[ed[tmp].t]) q[++top]=ed[tmp].t;
}
}
}
void print(int x)
{
printf("%.2d:",x/);
printf("%.2d ",x%);
}
int main()
{
n=read();
int x;
for(int i=;i<=n;i++)
{
//a[2i]-b[2i]前半程
//a[2i-1]-b[2i-1]后半程
a[*i]=read();
a[*i]=a[*i]*+read();
b[*i-]=read();
b[*i-]=b[*i-]*+read();
x=read();
b[*i]=a[*i]+x;
a[*i-]=b[*i-]-x;
}
build();
for(int i=;i<=*n;i++)
if(!dfn[i]) tarjan(i);
for(int i=;i<=n;i++)
if(belong[*i]==belong[*i-])
{puts("NO");return ;}
puts("YES");
rebuild();
for(int i=;i<=n;i++)
{
op[belong[*i]]=belong[*i-];
op[belong[*i-]]=belong[*i];
}
topsort();
for(int i=;i<=n;i++)
if(col[belong[*i]]==)
print(a[*i]),print(b[*i]),puts("");
else print(a[*i-]),print(b[*i-]),puts("");
return ;
}