2 条题解

  • 0
    @ 2025-10-8 16:59:09
    #include<bits/stdc++.h>
    using namespace std;
    const int N=3e3+10;
    vector<int>G[N];
    int c[N],cc[N];
    int tsp,cnt,dfn[N],low[N],scc[N];
    stack<int> stk;bool instk[N];
    void tarjan(int x)
    {
        dfn[x]=low[x]=++tsp;
        stk.push(x);instk[x]=1; 
        for(int y:G[x])
    	{
            if(!dfn[y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(instk[y]) low[x]=min(low[x],dfn[y]);
        }
        if(dfn[x]==low[x])
        {
            cnt++;
            for(int z=-1;z!=x;)
            {
                z=stk.top();stk.pop();instk[z]=0;
                scc[z]=cnt;
                cc[cnt]=min(c[z],cc[cnt]);
            }
        }
    }
    int main()
    {
        int n,m,p;scanf("%d%d",&n,&p);
        memset(c,0x3f,sizeof(c));
        for(int i=1,x;i<=p;i++){scanf("%d",&x);scanf("%d",&c[x]);}
         
        scanf("%d",&m);
        memset(G,0,sizeof(G));
        for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y);
         
        tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        memset(scc,0,sizeof(scc));memset(instk,false,sizeof(instk));
        memset(cc,0x3f,sizeof(cc));
        for(int i=1;i<=n;i++) if(!dfn[i] && c[i]!=0x3f3f3f3f) tarjan(i);
         
        vector<int>rd(cnt+1);
        for(int i=1,x,y;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j]) rd[scc[j]]++;
         
        for(int i=1;i<=n;i++)if(scc[i]==0){printf("NO\n%d",i);return 0;}
    
        int ans=0;for(int i=1;i<=cnt;i++)if(rd[i]==0)ans+=cc[i];
        printf("YES\n%d",ans);
    
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:58:53
      #include<bits/stdc++.h>
      using namespace std;
      const int N=3e3+10;
      vector<int>G[N];
      int c[N],cc[N];
      int tsp,cnt,dfn[N],low[N],scc[N];
      stack<int> stk;bool instk[N];
      void tarjan(int x)
      {
          dfn[x]=low[x]=++tsp;
          stk.push(x);instk[x]=1; 
          for(int y:G[x])
      	{
              if(!dfn[y])
              {
                  tarjan(y);
                  low[x]=min(low[x],low[y]);
              }
              else if(instk[y]) low[x]=min(low[x],dfn[y]);
          }
          if(dfn[x]==low[x])
          {
              cnt++;
              for(int z=-1;z!=x;)
              {
                  z=stk.top();stk.pop();instk[z]=0;
                  scc[z]=cnt;
                  cc[cnt]=min(c[z],cc[cnt]);
              }
          }
      }
      int main()
      {
          int n,m,p;scanf("%d%d",&n,&p);
          memset(c,0x3f,sizeof(c));
          for(int i=1,x;i<=p;i++){scanf("%d",&x);scanf("%d",&c[x]);}
           
          scanf("%d",&m);
          memset(G,0,sizeof(G));
          for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y);
           
          tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
          memset(scc,0,sizeof(scc));memset(instk,False,sizeof(instk));
          memset(cc,0x3f,sizeof(cc));
          for(int i=1;i<=n;i++) if(!dfn[i] && c[i]!=0x3f3f3f3f) tarjan(i);
           
          vector<int>rd(cnt+1);
          for(int i=1,x,y;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j]) rd[scc[j]]++;
           
          for(int i=1;i<=n;i++)if(scc[i]==0){printf("NO\n%d",i);return 0;}
      
          int ans=0;for(int i=1;i<=cnt;i++)if(rd[i]==0)ans+=cc[i];
          printf("YES\n%d",ans);
      
          return 0;
      }
      • 1

      *【强连通SCC】控制所有点[P1262] 间谍网络

      信息

      ID
      1878
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      76
      已通过
      19
      上传者