2 条题解

  • 0
    @ 2025-10-8 16:57:36
    #include <bits/stdc++.h>
    using namespace std;
    const int N=4100;
    vector<int> G[N];
    int match[N], chw[N], tsp;
    bool findmuniu(int x)
    {
        for(int y : G[x])
            if(chw[y] != tsp)
            {
                chw[y] = tsp;
                if( (match[y] == 0) || findmuniu(match[y]) )
                {
                    match[y] = x;
                    return 1;
                }
            }
        return 0;
    }
      
    int cnt, low[N], dfn[N], scc[N];
    stack<int> stk; bool instk[N];
     
    void tarjan(int x)
    {
        low[x] = dfn[x] = ++tsp;
        stk.push(x); instk[x] = True;
        for(int y : G[x])
        {
            if( dfn[y] == 0)
            {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if(instk[y]) low[x] = min(low[x], dfn[y]);
        }
        if( low[x] == dfn[x] )
        {
            cnt++;
            for(int z = -1; z != x; )
            {
                z = stk.top(); stk.pop(); instk[z] = 0;
                scc[z] = cnt;
            }
        }
    }
    int b[2100], blen;
    int main()
    {
        int n; scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            int k; scanf("%d", &k);
            for(int j=1, x; j<=k; j++) scanf("%d", &x), G[i].push_back(x + n);
        }
        memset(match, 0, sizeof(match));
        memset(chw, 0, sizeof(chw));
        tsp = 0; for(int i=1; i<=n; i++) tsp++, findmuniu(i);
         
        for(int i=1; i<=n; i++) G[i + n].push_back(match[i + n]);
           
        tsp = cnt = 0; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn));
        memset(scc, 0, sizeof(scc)); memset(instk, False, sizeof(instk));
        for(int i=1; i<=n + n; i++) if(dfn[i] == 0) tarjan(i);
        
        for(int i=1; i<=n; i++)
        {
            vector<int> V;
            for(int j : G[i]) if(scc[i] == scc[j]) V.push_back(j);
            sort(V.begin(), V.end());
            printf("%d ", V.size()); for(int j : V) printf("%d ", j - n); 
            printf("\n");
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:25
      #include<bits/stdc++.h>
      using namespace std;
      const int N=4100;
      vector<int>G[N];
      int match[N],chw[N],tsp;
      bool findmuniu(int x)
      {
          for(int y:G[x])
              if(chw[y]!=tsp)
              {
                  chw[y]=tsp;
                  if( (match[y]==0)||findmuniu(match[y]) )
                  {
                      match[y]=x;
                      return 1;
                  }
              }
          return 0;
      }
        
      int cnt,low[N],dfn[N],scc[N];
      stack<int>stk; bool instk[N];
       
      void tarjan(int x)
      {
          low[x]=dfn[x]=++tsp;
          stk.push(x);instk[x]=True;
          for(int y:G[x])
          {
              if( dfn[y]==0)
              {
                  tarjan(y);
                  low[x]=min(low[x],low[y]);
              }
              else if(instk[y]) low[x]=min(low[x],dfn[y]);
          }
          if( low[x]==dfn[x] )
          {
              cnt++;
              for(int z=-1;z!=x;)
              {
                  z=stk.top();stk.pop();instk[z]=0;
                  scc[z]=cnt;
              }
          }
      }
      int b[2100],blen;
      int main()
      {
          int n;scanf("%d",&n);
          for(int i=1;i<=n;i++)
          {
              int k;scanf("%d",&k);
              for(int j=1,x;j<=k;j++)scanf("%d",&x),G[i].push_back(x+n);
          }
          memset(match,0,sizeof(match));
          memset(chw,0,sizeof(chw));
          tsp=0;for(int i=1;i<=n;i++)tsp++,findmuniu(i);
           
          for(int i=1;i<=n;i++)G[i+n].push_back(match[i+n]);
             
          tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
          memset(scc,0,sizeof(scc));memset(instk,False,sizeof(instk));
          for(int i=1;i<=n+n;i++) if(dfn[i]==0) tarjan(i);
          
          for(int i=1;i<=n;i++)
          {
              vector<int>V;
              for(int j:G[i])if(scc[i]==scc[j]) V.push_back(j);
              sort(V.begin(),V.end());
              printf("%d ",V.size());for(int j:V) printf("%d ",j-n); 
              printf("\n");
          }
          return 0;
      }
      • 1

      *【强连通+匹配】国王的任务[POJ1904]

      信息

      ID
      1500
      时间
      1000ms
      内存
      64MiB
      难度
      7
      标签
      递交数
      152
      已通过
      30
      上传者