社区讨论

题目数据是不是有问题呀

P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 5已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@mi6gyu2h
此快照首次捕获于
2025/11/20 04:43
4 个月前
此快照最后确认于
2025/11/20 04:43
4 个月前
查看原帖
根据题意,应该是不会出现一头牛都不是明星的情况,然而测试点中出现了3个答案为0的情况;
这道题作为一道省选题(虽然历史很悠久),数据应当是有正版的,但是这里的测试点应该是自己出的;
本人代码已经在COGS和bzoj上AC了,在这里只能得76分。
综上,我认为这道题的数据应当尽快换成官方数据,这样才能最好地重现省选的情况。
本人的代码:
···c++
CPP
#include<cstdio>
const int N=1e4+10;
const int M=5e4+10;
struct edge
{
    int nxt,to;
}a[M<<1],e[M<<1];
int dfn[N],low[N],size[N],block[N],in[N];
int s[N],top;
int head[N],Head[N];
bool instack[N];
int vis[N];
int n,m,x,y,num,Num,tot,ans,Time,Size;
inline int min(const int &a,const int &b){return a<b?a:b;}
inline void add(int x,int y)
{
    a[++num].nxt=head[x],a[num].to=y,head[x]=num;
}
inline void add2(int x,int y)
{
    e[++Num].nxt=Head[x],e[Num].to=y,Head[x]=Num;
}
void dfs(int now)
{
    dfn[now]=low[now]=++Time;
    instack[now]=1;
    s[++top]=now;
    for(int i=head[now];i;i=a[i].nxt)
      if(!dfn[a[i].to])
      {
          dfs(a[i].to);
          low[now]=min(low[now],low[a[i].to]);
      }
      else if(instack[a[i].to]) low[now]=min(low[now],dfn[a[i].to]);
    if(low[now]==dfn[now])
    {
        tot++;
        int tmp;
        do tmp=s[top--],instack[tmp]=0,block[tmp]=tot,size[tot]++;
        while(tmp!=now);
    }
}
int Dfs(int now,int root)
{
    int ans=size[now];
    for(int i=Head[now];i;i=e[i].nxt)
      if(vis[a[i].to]!=root) vis[a[i].to]=root,ans+=Dfs(a[i].to,root);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
      scanf("%d%d",&x,&y),add(x,y);
    dfs(1);
    for(int j=1;j<=n;j++)
      for(int i=head[j];i;i=a[i].nxt)
        if(block[j]!=block[a[i].to]) add2(block[a[i].to],block[j]),in[block[j]]++;
    for(int i=1;i<=n;i++)
      if(!in[i])
      {
          int tmp=Dfs(i,i)-1;
          if(tmp==ans) Size+=size[i];
          else if(tmp>ans) Size=size[i],ans=tmp;
      }
    printf("%d",Size);
    return 0;
}
···

回复

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

正在加载回复...