1 条题解

  • 0
    @ 2025-5-6 23:37:49

    先判是否有解   然后对于 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
    上传者