2 条题解

  • 0
    @ 2025-10-8 16:58:03
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    vector<int>G[N];
    queue<int>q;
    int ind[N],f[N],milk[N];
    bool ism[N];
    int n,m,sum;
    void topo()
    {
        sum=0;memset(ism,0,sizeof(ism));memset(milk,0,sizeof(milk));
        for(int i=1;i<=n;i++)
        {
            if(!ind[i])
            {
                q.push(i);
                ism[i] = true;   //标记源点 
                milk[i] = 1;     //记录每个源点的流量
                sum++;           //一共有多少个源点(总流量)
            }
        }
        while(!q.empty())
        {
            int x= q.front();q.pop();
            if(G[x].size()>1) continue;   //某点的出度大于1,说明该点的后继节点不可能为关键点 
            for(int y:G[x])
            {
                ind[y]--;
                milk[y]+=milk[x];
                if(!ind[y]) q.push(y);
            }
        }
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1,x,y;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            ind[y]++;
        }
        topo();
        for(int i=1;i<=n;i++)
        {
            if(!ism[i]&&milk[i]==sum) //不是源点且来自所有源点的流量都流经该点 
            {
                printf("%d\n",i);
            }
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:53
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1e5+10;
      vector<int>G[N];
      queue<int>q;
      int ind[N],f[N],milk[N];
      bool ism[N];
      int n,m,sum;
      void topo()
      {
      	sum=0;memset(ism,0,sizeof(ism));memset(milk,0,sizeof(milk));
          for(int i=1;i<=n;i++)
          {
              if(!ind[i])
              {
                  q.push(i);
                  ism[i] = True;   //标记源点 
                  milk[i] = 1;     //记录每个源点的流量
                  sum++;           //一共有多少个源点(总流量)
              }
          }
          while(!q.empty())
          {
              int x= q.front();q.pop();
              if(G[x].size()>1) continue;   //某点的出度大于1,说明该点的后继节点不可能为关键点 
              for(int y:G[x])
              {
                  ind[y]--;
                  milk[y]+=milk[x];
                  if(!ind[y]) q.push(y);
              }
          }
      }
      int main()
      {
          scanf("%d",&n);
          for(int i=1,x,y;i<n;i++)
          {
              scanf("%d%d",&x,&y);
              G[x].push_back(y);
              ind[y]++;
          }
          topo();
          for(int i=1;i<=n;i++)
          {
              if(!ism[i]&&milk[i]==sum) //不是源点且来自所有源点的流量都流经该点 
              {
                  printf("%d\n",i);
              }
          }
          return 0;
      }
      • 1

      【拓扑】关键点[USACO10NOV] Chocolate Milk S

      信息

      ID
      1580
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      10
      已通过
      4
      上传者