社区讨论

其他平台可以AC,为什么洛谷不能ac

P1262间谍网络参与者 7已保存回复 6

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@mi4ezzlb
此快照首次捕获于
2025/11/18 18:12
4 个月前
此快照最后确认于
2025/11/18 18:12
4 个月前
查看原帖
CPP
#include<stdio.h>
int n,p,r,min,flag,s;
int m[3010],a[3010][3010],f[3010],t[3010],c[3010],d[3010];
void dfs(int k)
{
    int i;
    for(i=1;i<=n;i++)
    if(a[k][i]&&f[i]==0)
    {
        f[i]=1;
        dfs(i); 
     }     
}
int main()
{
    int i,x,y,j,tmp;
    scanf("%d%d",&n,&p);
    for(i=1;i<=p;i++)
    {
        scanf("%d%d",&x,&y);
        m[x]=y;
        c[x]=x;
    }
    scanf("%d",&r);
    for(i=1;i<=r;i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]=1;
        t[y]++;
        d[x]++;
    }
   for(i=1;i<=n;i++)
   {
         if(m[i]&&t[i]==0&&f[i]==0)  //找到入度支付资金 
         {
             s=s+m[i];
             f[i]=1;
             dfs(i);
      }
   }
   for(i=1;i<=n-1;i++)
    for(j=1;j<=n-i;j++)
    if(m[j]>m[j+1])
    {
        tmp=m[j];m[j]=m[j+1];m[j+1]=tmp;
        tmp=c[j];c[j]=c[j+1];c[j+1]=tmp;
    }
    for(i=1;i<=n;i++)
    {
        if(m[i]&&f[c[i]]==0&&d[c[i]])
        {
            s=s+m[i];
               f[c[i]]=1;
                 dfs(c[i]);
        }    
    }
    for(i=1;i<=n;i++)
     if(f[i]==0)
     {
         flag=1;
         printf("NO\n%d\n",i);
         break;    
     }
  if(flag==0)printf("YES\n%d\n",s);
    return 0;
}

回复

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

正在加载回复...