做网站后都需要什么,品牌建设的作用和意义,建设银行关方网站,中企动力公司是做什么的题目链接#xff1a;http://poj.org/problem?id3683 题意#xff1a;有n个婚礼要举行#xff0c;但是只有一个牧师。第i个婚礼使用牧师的时间长为leni#xff0c;可以在开始时或结束时使用。问能否使得n个婚礼均举行#xff1f; 思路:对于婚礼i#xff0c;i*2-1表示在开…题目链接http://poj.org/problem?id3683 题意有n个婚礼要举行但是只有一个牧师。第i个婚礼使用牧师的时间长为leni可以在开始时或结束时使用。问能否使得n个婚礼均举行 思路:对于婚礼ii*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 MAX4005;const int MAXE5000005;node edges[MAXE];int head[MAX],e;int dfn[MAX],low[MAX],visit[MAX],color[MAX],col[MAX];int n,index,cnt;stackint S;int deg[MAX],ans[MAX],p[MAX];int head1[MAX],e1;node edges1[MAXE];void Add(int u,int v){edges[e].vv;edges[e].nexthead[u];head[u]e;}void Add1(int u,int v){edges1[e1].vv;edges1[e1].nexthead1[u];head1[u]e1;}void Tarjan(int u){int i,v;low[u]dfn[u]index;S.push(u);visit[u]1;for(ihead[u];i!-1;iedges[i].next){vedges[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{vS.top();S.pop();visit[v]0;color[v]cnt;}while(u!v);}}void init(){memset(deg,0,sizeof(deg));memset(head1,-1,sizeof(head1));e10;int i,u,v,x,y;for(u1;u2*n;u){for(ihead[u];i!-1;iedges[i].next){vedges[i].v;if(color[v]!color[u]){xcolor[v];ycolor[u];Add1(x,y);deg[y];}}}while(!S.empty()) S.pop();for(i1;icnt;i) if(!deg[i]) S.push(i);memset(p,0,sizeof(p));while(!S.empty()){uS.top();S.pop();if(!p[u]) p[u]1,p[col[u]]-1;for(ihead1[u];i!-1;iedges1[i].next){vedges1[i].v;if(--deg[v]0) S.push(v);}}memset(ans,0,sizeof(ans));for(i1;in;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));indexcnt0;while(!S.empty()) S.pop();for(i1;i2*n;i) if(!dfn[i]) Tarjan(i);for(i1;in;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(i1;in;i){ans[i]?(xa[i].s,ya[i].sa[i].len):(xa[i].e-a[i].len,ya[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 s1s2len2s2s1len1;}int main(){while(scanf(%d,n)!-1){int i,j,h1,m1,h2,m2;for(i1;in;i){scanf(%d:%d %d:%d %d,h1,m1,h2,m2,a[i].len);a[i].sh1*60m1;a[i].eh2*60m2;}memset(head,-1,sizeof(head));e0;int u,v;for(i1;in;i) for(j1;jn;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;}