題目鏈接：http://poj.org/problem?id=3683
題意：有n個婚禮要舉行，但是只有一個牧師。第i個婚禮使用牧師的時間長為leni，可以在開始時或結束時使用。問能否使得n個婚禮均舉行？
思路:對于婚禮i，i*2-1表示在開始使用牧師，i*2表示在結束使用牧師。枚舉每一對不同的i和j：
（1）如果i*2-1和j*2-1沖突。連接i*2-1 ?j*2
（2）如果i*2-1和j*2沖突，連接i*2-1 j*2-1
（3）如果i*2和j*2-1沖突，連接i*2 j*2
（4）如果i*2和j*2沖突，連接i*2 j*2-1
?
#include <stdio.h>#include <string.h>#include <stack>#define min(x,y) ((x)<(y)?(x):(y))using namespace std;struct node{int v,next;};const int MAX=4005;const int MAXE=5000005;node edges[MAXE];int head[MAX],e;int dfn[MAX],low[MAX],visit[MAX],color[MAX],col[MAX];int n,index,cnt;stack<int> S;int deg[MAX],ans[MAX],p[MAX];int head1[MAX],e1;node edges1[MAXE];void Add(int u,int v){edges[e].v=v;edges[e].next=head[u];head[u]=e++;}void Add1(int u,int v){edges1[e1].v=v;edges1[e1].next=head1[u];head1[u]=e1++;}void Tarjan(int u){int i,v;low[u]=dfn[u]=++index;S.push(u);visit[u]=1;for(i=head[u];i!=-1;i=edges[i].next){v=edges[i].v;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(visit[v]) low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){cnt++;do{v=S.top();S.pop();visit[v]=0;color[v]=cnt;}while(u!=v);}}void init(){memset(deg,0,sizeof(deg));memset(head1,-1,sizeof(head1));e1=0;int i,u,v,x,y;for(u=1;u<=2*n;u++){for(i=head[u];i!=-1;i=edges[i].next){v=edges[i].v;if(color[v]!=color[u]){x=color[v];y=color[u];Add1(x,y);deg[y]++;}}}while(!S.empty()) S.pop();for(i=1;i<=cnt;i++) if(!deg[i]) S.push(i);memset(p,0,sizeof(p));while(!S.empty()){u=S.top();S.pop();if(!p[u]) p[u]=1,p[col[u]]=-1;for(i=head1[u];i!=-1;i=edges1[i].next){v=edges1[i].v;if(--deg[v]==0) S.push(v);}}memset(ans,0,sizeof(ans));for(i=1;i<=n;i++){if(p[color[i*2-1]]==1) ans[i]=1;}}int TWO_ST(){int i;memset(dfn,0,sizeof(dfn));memset(visit,0,sizeof(visit));index=cnt=0;while(!S.empty()) S.pop();for(i=1;i<=2*n;i++) if(!dfn[i]) Tarjan(i);for(i=1;i<=n;i++){if(color[i*2-1]==color[i*2]) return 0;col[color[i*2-1]]=color[i*2];col[color[i*2]]=color[i*2-1];}init();return 1;}struct Node{int s,e,len;};Node a[MAX];void deal(){if(!TWO_ST()){puts("NO");return;}puts("YES");int i,x,y;for(i=1;i<=n;i++){ans[i]?(x=a[i].s,y=a[i].s+a[i].len):(x=a[i].e-a[i].len,y=a[i].e);printf("%02d:%02d %02d:%02d\n",x/60,x%60,y/60,y%60);}}int OK(int s1,int len1,int s2,int len2){return s1<s2+len2&&s2<s1+len1;}int main(){while(scanf("%d",&n)!=-1){int i,j,h1,m1,h2,m2;for(i=1;i<=n;i++){scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&a[i].len);a[i].s=h1*60+m1;a[i].e=h2*60+m2;}memset(head,-1,sizeof(head));e=0;int u,v;for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j){if(OK(a[i].s,a[i].len,a[j].s,a[j].len)) Add(i*2-1,j*2);if(OK(a[i].s,a[i].len,a[j].e-a[j].len,a[j].len)) Add(i*2-1,j*2-1);if(OK(a[i].e-a[i].len,a[i].len,a[j].s,a[j].len)) Add(i*2,j*2);if(OK(a[i].e-a[i].len,a[i].len,a[j].e-a[j].len,a[j].len)) Add(i*2,j*2-1);}deal();}return 0;}
?
?
?
