社区讨论

90分求助QAQ

P3254圆桌问题参与者 3已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mi6o1wga
此快照首次捕获于
2025/11/20 08:01
4 个月前
此快照最后确认于
2025/11/20 08:01
4 个月前
查看原帖
第三个点WA了
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=10086;
const int maxm=200086;
const int inf=99999999;
int head[maxn],next[maxm],ass,to[maxm],w[maxm],dep[maxn],j,k,l,n,m,s,t,cnt=-1,from[maxm],cur[maxn];
inline int add(int x,int y,int z){
    to[++cnt]=y;from[cnt]=x;next[cnt]=head[x];w[cnt]=z;head[x]=cnt;
}
inline int Read(){
    int x=0;char c=getchar();
    while (!isdigit(c)){
        c=getchar();
    }
    while (isdigit(c)){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }return x;
}
bool bfs(){
    queue<int> q;
    memset(dep,0,sizeof(dep));
    q.push(s);dep[s]=1;
    while (!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i!=-1;i=next[i]){
            int v=to[i];
            if (dep[v]==0&&w[i]>0){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if (dep[t])return 1;
    else return 0;
}
inline int dfs(int x,int dist){
    if (x==t)return dist;
    for (int& i=cur[x];i!=-1;i=next[i]){
        int v=to[i];
        if (dep[v]==dep[x]+1&&w[i]!=0){
            int d=dfs(v,min(dist,w[i]));
            if (d){
                w[i]-=d;
                w[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while (bfs()){
        for (int i=0;i<=maxn-1;i++)cur[i]=head[i];
        while (int di=dfs(s,inf))ans+=di;
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    m=Read();n=Read();s=0;t=n+m+1;
    for (int i=1;i<=m;i++){
        for (j=1;j<=n;j++){
            add(i,j+m,1);add(j+m,i,0);
        }
    }
    for (int i=1;i<=m;i++){
        k=Read();add(s,i,k);add(i,s,0);
    }
    for (int i=1;i<=n;i++){
        k=Read();add(i+m,t,k);add(t,i+m,0);
    }
    ass=dinic();
    if (ass){
        printf("1\n");
        for (int o=1;o<=m;o++){
            int faq=1;
            for (int i=head[o];i!=-1;i=next[i]){
                if (to[i]>m&&to[i]<=m+n&&w[i]==0){
                    if (faq!=1)printf(" ");
                    faq++;
                    printf("%d",to[i]-m);
                }
            }
            printf("\n");
        }
    }
    else printf("0");
    return 0;
}
(是不是SPJ有问题)

回复

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

正在加载回复...