社区讨论
题目数据是不是有问题呀
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 条回复,欢迎继续交流。
正在加载回复...