发现建图的方法各有不同，前面一题连边和这一题连边建图的点就不同，感觉这题的建图方案更好。
题意：给出每个婚礼的2个主持时间，每个婚礼的可能能会冲突，输出方案。
思路：n个婚礼，2*n个点，每组点是对称的，用O(n2)的方法判断每个点之间的关系来建图，然后通过拓扑排序输出即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 2002
int instack[MAXN],stack[MAXN],fa[MAXN],vis[MAXN],head[MAXN],first[MAXN];
int dfn[MAXN],low[MAXN],in[MAXN],ans[MAXN];
int a[MAXN][2],b[MAXN][2],flag[MAXN];
int n,m,tot,scnt,time,tt,top,index; struct Edge
{
int v,next;
}edge[MAXN*MAXN],e[MAXN*MAXN]; void addedge(int u,int v)
{
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void adde(int u,int v)
{
e[tt].v=v;
e[tt].next=first[u];
first[u]=tt++;
}
void print(int t)
{
int h=t/60,m=t%60;
printf("%02d:%02d",h,m);
} void tarjan(int u)
{
instack[u]=1;
stack[top++]=u;
dfn[u]=low[u]=++index;
int v;
for(int i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scnt++;
do
{
v=stack[--top];
instack[v]=0;
fa[v]=scnt;
}while(v!=u);
}
}
void build()
{
for(int i=0;i<n;i++) //有2n个点 2*i 代表起始时间 2*i+1代表结束时间
{
for(int j=i+1;j<n;j++)
{
if((a[i][1]-a[j][0])*(a[i][0]-a[j][1])<0) //前 前冲突
{
addedge(i*2,2*j+1);
addedge(j*2,2*i+1);
}
if((a[i][1]-b[j][0])*(a[i][0]-b[j][1])<0) //前 后
{
addedge(i*2,2*j);
addedge(j*2+1,2*i+1);
}
if((b[i][1]-b[j][0])*(b[i][0]-b[j][1])<0) //后后
{
addedge(2*i+1,2*j);
addedge(2*j+1,2*i);
}
if((b[i][1]-a[j][0])*(b[i][0]-a[j][1])<0) //后前
{
addedge(2*i+1,2*j+1);
addedge(2*j,2*i);
}
}
}
}
void solve()
{
memset(dfn,0,sizeof(dfn));
memset(instack,0,sizeof(instack));
index=0;scnt=0;
for(int i=0;i<2*n;i++)
{
if(!dfn[i])
tarjan(i);
}
}
int check()
{
for(int i=0;i<n;i++)
{
if(fa[2*i]==fa[2*n+1]) //冲突
{
return 0;
}
}
return 1;
}
void topsort()
{ for(int i=0;i<scnt;)
{
for(int j=1;j<=scnt;j++)
{
if(!in[j])
{
in[j]--;ans[i++]=j;
for(int k=first[j];k!=-1;k=e[k].next)
{
int v=e[k].v;
in[v]--;
}
}
}
}
memset(flag,0,sizeof(flag));
for(int i=0;i<scnt;i++)
{
for(int j=0;j<2*n;j++)
{
if(fa[j]==ans[i]&&!flag[j^1])
{ flag[j]=1;
}
}
}
for(int i=0;i<2*n;i++)
{
if(flag[i])
{
if(i%2==0)
{
print(a[i/2][0]);printf(" ");print(a[i/2][1]);printf("\n");
}
else
{
print(b[i/2][0]);printf(" ");print(b[i/2][1]);printf("\n");
}
}
}
}
int main()
{
scanf("%d",&n);
memset(head,-1,sizeof(head));tot=0;
memset(first,-1,sizeof(first));tt=0;
for(int i=0;i<n;i++)
{
int t1,t2;
scanf("%d:%d",&t1,&t2);
a[i][0]=t1*60+t2;
scanf("%d:%d",&t1,&t2);
b[i][1]=t1*60+t2;
scanf("%d",&time);
a[i][1]=a[i][0]+time;
b[i][0]=b[i][1]-time;
}
build();
solve();
if(!check())printf("NO\n");
else
{
memset(in,0,sizeof(in));
for(int i=0;i<2*n;i++)
{
int v;
for(int j=head[i];j!=-1;j=edge[j].next)
{
v=edge[j].v;
if(fa[i]!=fa[v])
{
adde(fa[v],fa[i]);
in[fa[i]]++;
}
}
}
printf("YES\n");
topsort();
} return 0;
}