捞帖 代码清晰 求帮调
查看原帖
捞帖 代码清晰 求帮调
178259
anideahe楼主2022/1/3 16:52
#include<cstdio>
#include<cstring>
using namespace std;
int min(int x,int y){return x<y?x:y;}
const int N=5e3+1;
struct edge{int next,to,w,cost;}d[N];
int head[N],cnt=1;
void add(int x,int y,int w,int c){
    d[++cnt]=(edge){head[x],y,w, c};head[x]=cnt;
    d[++cnt]=(edge){head[y],x,0,-c};head[y]=cnt;
}
int n,a[N][N],p[N],q[N],pre[N],dis[N],flow[N];
int bfs_max(){
    int l=0,r=1;
    memset(q,0,sizeof 0);
    memset(p,0,sizeof 0);
    memset(pre,0,sizeof 0);
    for(int i=0;i<N;i=-~i) dis[i]=-0x3f3f3f3f;
    memset(flow,0x3f,sizeof flow);
    p[0]=1,q[1]=dis[0]=0;
    while(l<r){
        int x=q[++l];
        p[x]=0;
        if(x==2*n+1) return 1;
        for(int i=head[x];i;i=d[i].next){
            int v=d[i].to,w=d[i].w,c=d[i].cost;
            if(w>0&&dis[x]+c>=dis[v]){
                pre[v]=i;
                if(!p[v]){p[v]=1;q[++r]=v;}
                dis[v]=dis[x]+c;
                flow[v]=min(flow[x],w);
            }
        }
    }
    return 0;
}
int bfs_min(){
    int l=0,r=1;
    memset(q,0,sizeof 0);
    memset(p,0,sizeof 0);
    memset(pre,0,sizeof 0);
    memset(dis,0x3f,sizeof dis);
    memset(flow,0x3f,sizeof flow);
    p[0]=1,q[1]=dis[0]=0;
    while(l<r){
        int x=q[++l];
        p[x]=0;
        if(x==2*n+1) return 1;
        for(int i=head[x];i;i=d[i].next){
            int v=d[i].to,w=d[i].w,c=d[i].cost;
            if(w>0&&dis[x]+c<=dis[v]){
                pre[v]=i;
                if(!p[v]){p[v]=1;q[++r]=v;}
                dis[v]=dis[x]+c;
                flow[v]=min(flow[x],w);
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i=-~i){
        for(int j=1;j<=n;j=-~j){
            scanf("%d",&a[i][j]);
            add(i,j+n,1,a[i][j]);
        }
        add(0,i,1,0),add(i+n,2*n+1,1,0);
    }
    int s=0,t=2*n+1,ans=0;
    while(bfs_min()){
        ans+=dis[t]*flow[t];
        int now=t;
        while(now!=s){
            d[pre[now]].w-=flow[t];
            d[pre[now]^1].w+=flow[t];
            now=d[pre[now]^1].to;
        }
    }
    printf("%d\n",ans);
    for(int i=2;i<=cnt;i+=2){
        d[i].w+=d[i^1].w;
        d[i^1].w=0;
    } 
    ans=0;
    while(bfs_max()){
        ans+=dis[t]*flow[t];
        int now=t;
        while(now!=s){
            d[pre[now]].w-=flow[t];
            d[pre[now]^1].w+=flow[t];
            now=d[pre[now]^1].to;
        }
    }
    printf("%d\n",ans);
    return 0;
}
2022/1/3 16:52
加载中...