社区讨论

为什么必须要加一个无关紧要的东西才能A

LL______
P2765魔术球问题参与者 12已保存回复 26

讨论操作

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

当前回复
26 条
当前快照
1 份
快照标识符
@mi7w0ejq
此快照首次捕获于
2025/11/21 04:32
4 个月前
此快照最后确认于
2025/11/21 06:47
4 个月前
查看原帖
如题，代码参考题解，两个代码完全一样，但是在第8行随便添加了一个没有用到的数组或者变量就能AC，但是只要把这第8行删去或者移位就会全WA
下贴代码
第一个AC
CPP
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int k=1,n,s=0,t=50010;
int asdga;
int head[50010],next[100010],to[100010],w[100010];
int ans,dep[100010],xia[100010],vis[100010],top[100];

void add(int x,int y,int z)
{
    to[++k]=y;
    w[k]=z;
    next[k]=head[x];
    head[x]=k;
    
    to[++k]=x;
    w[k]=0;
    next[k]=head[y];
    head[y]=k;
}
int bfs()
{
    queue<int> q;
	q.push(s);
    memset(dep,0,sizeof(dep));dep[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=next[i]){
            int v=to[i];
            if(dep[v]||w[i]<=0)continue;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
    return dep[t];
}
int dfs(int x,int flow){
    if(x==t) return flow;
    int k;
    for(int i=head[x];i;i=next[i]){
        int u=to[i];
        if(dep[u]!=dep[x]+1||w[i]<=0) continue;
        if(k=dfs(u,min(w[i],flow))){
            w[i]-=k;w[i^1]+=k;
            if(u!=t) xia[x>>1]=u>>1;
            return k;
        }
    }
    return 0;
}
int dinic(){
    int k=0;
    while(bfs()){
        while(1){
            int p=dfs(s,1e9);
            if(!p) break;
            k+=p;
        }
    }
    return k;
}
int main()
{
    scanf("%d",&n);
    int now=0,cnt=0;
    while(now<=n){
        cnt++;
        add(s,cnt<<1,1);add((cnt<<1)|1,t,1);
        for(int i=sqrt(cnt)+1;i*i<2*cnt;++i){
        	add((i*i-cnt)<<1,(cnt<<1)|1,1);
		}
        int k=dinic();
        if(!k)top[++now]=cnt;
    }
    printf("%d\n",cnt-1);
    for(int i=1;i<=n;++i){
        if(vis[top[i]]) continue;
        int x=top[i];vis[x]=1;
        while(x!=0){
        	printf("%d ",x);
            x=xia[x];vis[x]=1;
        }
        printf("\n");
    }
    return 0;
}
第二个全WA
CPP
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int k=1,n,s=0,t=50010;
//这里不加东西
int head[50010],next[100010],to[100010],w[100010];
int ans,dep[100010],xia[100010],vis[100010],top[100];

void add(int x,int y,int z)
{
    to[++k]=y;
    w[k]=z;
    next[k]=head[x];
    head[x]=k;
    
    to[++k]=x;
    w[k]=0;
    next[k]=head[y];
    head[y]=k;
}
int bfs()
{
    queue<int> q;
	q.push(s);
    memset(dep,0,sizeof(dep));dep[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=next[i]){
            int v=to[i];
            if(dep[v]||w[i]<=0)continue;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
    return dep[t];
}
int dfs(int x,int flow){
    if(x==t) return flow;
    int k;
    for(int i=head[x];i;i=next[i]){
        int u=to[i];
        if(dep[u]!=dep[x]+1||w[i]<=0) continue;
        if(k=dfs(u,min(w[i],flow))){
            w[i]-=k;w[i^1]+=k;
            if(u!=t) xia[x>>1]=u>>1;
            return k;
        }
    }
    return 0;
}
int dinic(){
    int k=0;
    while(bfs()){
        while(1){
            int p=dfs(s,1e9);
            if(!p) break;
            k+=p;
        }
    }
    return k;
}
int main()
{
    scanf("%d",&n);
    int now=0,cnt=0;
    while(now<=n){
        cnt++;
        add(s,cnt<<1,1);add((cnt<<1)|1,t,1);
        for(int i=sqrt(cnt)+1;i*i<2*cnt;++i){
        	add((i*i-cnt)<<1,(cnt<<1)|1,1);
		}
        int k=dinic();
        if(!k)top[++now]=cnt;
    }
    printf("%d\n",cnt-1);
    for(int i=1;i<=n;++i){
        if(vis[top[i]]) continue;
        int x=top[i];vis[x]=1;
        while(x!=0){
        	printf("%d ",x);
            x=xia[x];vis[x]=1;
        }
        printf("\n");
    }
    return 0;
}
求大佬看看我是哪里有问题
感谢各位大佬

回复

共 26 条回复，欢迎继续交流。

正在加载回复...