1 条题解

  • 0
    @ 2024-12-24 10:06:04

    C++ :

    #include<iostream>
    using namespace std;
    int a[10001][301]={0},into[10001],ans[10001],m,n,money;
    void init()                             //读入数据,并构建图,统计入度
    { int i,x,y;
      cin>>n>>m;
      for(i=1;i<=m;i++)
       {
         cin>>x>>y;
         a[y][0]++;                         //记录由y引出边的数目
         a[y][a[y][0]]=x;                 //记录由a[y][0]引出边的顶点
         into[x]++;                         //统计入度
       }
    }
    bool topsort()                        //拓扑排序
    { int t,tot,k,i,j;
      tot=0;k=0;
      while(tot<n)                         //tot顶点个数
       {
        t=0;                                    //用来判断有无环
        for(i=1;i<=n;i++)
          if(into[i]==0)
          {
            tot++;t++;money+=100;
            ans[t]=i;
            into[i]=0xfffffff;
           }
       if(t==0)return false;               //存在环
       money+=k*t;k++;
       for(i=1;i<=t;i++)                     //去掉相连的边
         for(j=1;j<=a[ans[i]][0];j++)into[a[ans[i]][j]]--;
      }
      return true;
    }
    int main()
    {
      init();money=0;
      if(topsort())cout<<money<<endl;
         else cout<<"Poor Xed"<<endl;
      return 0;
    }
    
    
    • 1

    信息

    ID
    1855
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者