1 条题解
-
0
先判是否有解 然后对于 A 和 'A 它们所在的联通块是不能同时选的 重新建图 拓扑一下搞出顺序 就完了
//poj3683 #include <cstdio> #include <algorithm> using namespace std; const int N=1e3+5; int n,cnt,_cnt; int S1[N],T1[N],S2[N],T2[N],last[N<<1],_last[N<<1]; int op[N<<1]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool judge(int S1,int T1,int S2,int T2){ if(T1<=S2 || S1>=T2)return 0; return 1; } struct edge{ int to,next; }e[(N*N)<<2],_e[(N*N)<<2]; void add_edge(int u,int v){ e[++cnt]=(edge){v,last[u]};last[u]=cnt; } int in[N<<1]; void _add_edge(int u,int v){ in[v]++; _e[++_cnt]=(edge){v,_last[u]};_last[u]=_cnt; } int ind,top,scc; int q[N<<1],dfn[N<<1],low[N<<1],col[N<<1]; bool inq[N<<1]; void Tarjan(int u){ dfn[u]=low[u]=++ind; q[++top]=u;inq[u]=1; for(int i=last[u];i;i=e[i].next){ int v=e[i].to; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else if(inq[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ int now=0;scc++; while(now!=u){ now=q[top--]; col[now]=scc; inq[now]=0; } } } int mark[N<<1]; void dfs(int u){ if(mark[u])return; mark[u]=-1; for(int i=_last[u];i;i=_e[i].next) dfs(_e[i].to); } void topsort(){ top=0; for(int i=1;i<=scc;i++) if(!in[i])q[++top]=i; while(top){ int u=q[top--]; if(mark[u])continue; mark[u]=1;dfs(op[u]); for(int i=_last[u];i;i=_e[i].next){ int v=_e[i].to; in[v]--; if(!in[v])q[++top]=v; } } } void print(int x){ printf("%.2d:",x/60); printf("%.2d ",x%60); } int main(){ n=read(); for(int i=1;i<=n;i++){ S1[i]=read()*60+read(); T2[i]=read()*60+read(); int x=read(); T1[i]=S1[i]+x; S2[i]=T2[i]-x; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(judge(S1[i],T1[i],S1[j],T1[j])){ add_edge(i*2,j*2-1); add_edge(j*2,i*2-1); } if(judge(S1[i],T1[i],S2[j],T2[j])){ add_edge(i*2,j*2); add_edge(j*2-1,i*2-1); } if(judge(S2[i],T2[i],S1[j],T1[j])){ add_edge(i*2-1,j*2-1); add_edge(j*2,i*2); } if(judge(S2[i],T2[i],S2[j],T2[j])){ add_edge(i*2-1,j*2); add_edge(j*2-1,i*2); } } for(int i=1;i<=n*2;i++) if(!dfn[i])Tarjan(i); for(int i=1;i<=n;i++) if(col[i*2-1]==col[i*2]){ puts("NO"); return 0; } puts("YES"); for(int u=1;u<=2*n;u++) for(int i=last[u];i;i=e[i].next) if(col[u]!=col[e[i].to]) _add_edge(col[e[i].to],col[u]); for(int i=1;i<=n;i++){ op[col[i*2]]=col[i*2-1]; op[col[i*2-1]]=col[i*2]; } topsort(); for(int i=1;i<=n;i++) if(mark[col[i*2]]==1) print(S1[i]),print(T1[i]),puts(""); else print(S2[i]),print(T2[i]),puts(""); return 0; }
- 1
信息
- ID
- 2684
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者