社区讨论

求大佬解答为何全T?

P3243[HNOI2015] 菜肴制作参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6z9ngj
此快照首次捕获于
2025/11/20 13:15
4 个月前
此快照最后确认于
2025/11/20 13:15
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
  const int N=100001;
  int n,m,x,y,head,tail,cnt,sum,top;
  int p[N],v[N],h[N],h1[N],num[N],vis[N],que[N*3];
  struct Edge{
  int to,nxt;
  }s[N*2],e[N*2];
  struct fuck{
    bool operator()(int a,int b)
    {
      return (num[a]==num[b])? a>b:num[a]>num[b];
    }
  };
  priority_queue<int,vector<int>,fuck >q;
  inline void add(int x,int y)
  {
    cnt++;
    s[cnt].to=y;
    s[cnt].nxt=h[x];
    h[x]=cnt;
    e[cnt].to=x;
    e[cnt].nxt=h1[y];
    h1[y]=cnt;
  }
  inline int read()
  {
    int x=0,ff=1;
    char c;
    c=getchar();
    while(c<'0' || c>'9'){ if (c=='-') ff=-1; c=getchar(); }
    while(c>='0' && c<='9') { x=x*10+c-48; c=getchar(); }
    return x*ff;
  }
  int main()
  {
    freopen("fa.in","r",stdin);
    freopen("fa.out","w",stdout);
    register int T=read();  
    while(T--)
    {
      memset(s,0,sizeof(s));
      memset(p,0,sizeof(p));
      memset(h,0,sizeof(h));
      memset(vis,0,sizeof(vis));
      memset(num,0,sizeof(num));
      memset(que,0,sizeof(que));
      memset(v,0,sizeof(v));
      memset(h1,0,sizeof(h1));
      memset(e,0,sizeof(e));
      cnt=0; head=0; tail=0;
      n=read(); m=read();
      for(register int i=1;i<=m;++i)
      {
        x=read(); y=read();
        add(x,y);
        v[x]++; p[y]++;
      }
      for(register int i=1;i<=n;++i)
        if (p[i]==0) q.push(i);
        if (q.empty()) { printf("Impossible!\n"); continue; }
      for(register int i=1;i<=n;++i)
      if (v[i]==0) { que[++tail]=i; vis[i]=1; num[i]=i; }
      while(head<tail)
      {
        head++;
        register int d=que[head];
        for(register int i=h1[d];i;i=e[i].nxt)
        {
          register int a=e[i].to;
          if (!vis[a]) { vis[a]=1; que[++tail]=a; }
          num[a]=(num[a]==0)? min(a,num[d]):min(num[a],min(a,num[d]));
        }
      }
        while(!q.empty())
        {
          register int k=q.top();
          printf("%d ",k);
          q.pop();
          for(register int i=h[k];i;i=s[i].nxt)
          {
            register int l=s[i].to;
            p[l]--;
            if (p[l]==0) q.push(l);
          }
        }
        printf("\n");
    }
    return 0;
  }
反向拓扑一遍求每个点到最后一个点最小的节点编号存在num数组里。全T了QAQ

回复

2 条回复,欢迎继续交流。

正在加载回复...