LG2045 方格取数加强版 费用流

问题描述

LG2045

题解

费用流。

套路拆点，把\((i,j)\)拆为两个点，在这两个点之间连边：一条边流量为\(1\)，费用为\(a_{i,j}\)，另一条边为流量为\(INF\)，费用为\(0\)（表示联通）。

然后在\((i,j)\)的出点向\((i+1,j)\)，\((i,j+1)\)连边，流量\(INF\)，费用\(0\)，表示联通。

建立\(S,T\)，分别于\((1,1),(n,n)\)相连，流量为\(k\)，费用为\(0\)，代表可以走\(k\)次。

跑费用最大流即可。

传纸条本质是本题的特殊情况，即\(k=2\)的情况

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=53;
const int maxm=1000000;
const int INF=0x3f3f3f3f;

int a[maxn][maxn],n,k;

int Head[maxn*maxn*2],S,T;
int Next[maxm],to[maxm],tot=1,w[maxm],cost[maxm];

void add(int x,int y,int z,int c){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z,cost[tot]=c;
}

int calc(int x,int y,int t){
    return (x-1)*n+y+(t-1)*n*n;
}

bool vis[maxm];
int dis[maxm],pre[maxm],now[maxm];
bool spfa(){
    memset(vis,0,sizeof(vis));memset(dis,0xcf,sizeof(dis));
    memset(pre,0,sizeof(pre));
    queue<int>q;q.push(S);vis[S]=1,dis[S]=0;
    now[S]=INF;
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i],len=w[i],ct=cost[i];
            if(!len||dis[y]>=dis[x]+ct) continue;
            dis[y]=dis[x]+ct;now[y]=min(now[x],len);
            pre[y]=i;
            if(!vis[y]) q.push(y),vis[y]=1;
        }
    }
    return dis[T]!=0xcfcfcfcf;
}

int mx,ans;

void upd(){
    mx+=now[T],ans+=dis[T]*now[T];
    int p=T;
    while(p!=S){
        int k=pre[p];
        w[k]-=now[T],w[k xor 1]+=now[T];
        p=to[k xor 1];
    }
}

int main(){
    read(n);read(k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            read(a[i][j]);
        }
    }
    S=n*n*2+1,T=S+1;
    add(S,calc(1,1,1),k,0);add(calc(1,1,1),S,0,0);
    add(calc(n,n,2),T,k,0);add(T,calc(n,n,2),0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            add(calc(i,j,1),calc(i,j,2),1,a[i][j]);add(calc(i,j,2),calc(i,j,1),0,-a[i][j]);
            add(calc(i,j,1),calc(i,j,2),INF,0);add(calc(i,j,2),calc(i,j,1),0,0);
            if(i!=n) add(calc(i,j,2),calc(i+1,j,1),INF,0),add(calc(i+1,j,1),calc(i,j,2),0,0);
            if(j!=n) add(calc(i,j,2),calc(i,j+1,1),INF,0),add(calc(i,j+1,1),calc(i,j,2),0,0);
        }
    }
    while(spfa())
        upd();
    printf("%d\n",ans);
    return 0;
}