【Luogu】P3159交换棋子（超出我能力范围的费用流）

　　题目链接

　　明显超出我能力范围。

　　只放题解。

　　再放代码。

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<queue>

#define maxn 100200

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int n,m;

inline int calc(int x,int y,int z){    return (x-)*m+y+(z-)*(n*m);    }

inline int count(int i){    return i&?i+:i-;    }

struct Edge{

    int from,next,to,dis,val,flow;

}edge[maxn];

int head[maxn],num;

inline void addedge(int from,int to,int dis,int val){

    edge[++num]=(Edge){from,head[from],to,dis,val,};

    head[from]=num;

}

inline void add(int from,int to,int dis,int val){

    addedge(from,to,dis,val);

    addedge(to,from,-dis,);

}

bool sta[][];

bool edn[][];

int swa[][];

int Start,End;

int u[]={,,,,,,-,-,-};

int w[]={,,,,-,-,-,,};

struct Ans{

    long long dis,val;

    Ans(){dis=val=;}

};

long long dis[maxn];

long long pre[maxn];

int flow[maxn];

bool vis[maxn];

int sum;

Ans spfa(){

    Ans ans;

    memset(dis,/,sizeof(dis));    long long Max=dis[];

    dis[Start]=;    flow[Start]=0x7fffffff;

    queue<int>q;    q.push(Start);

    while(!q.empty()){

        int from=q.front();q.pop();vis[from]=;

        for(int i=head[from];i;i=edge[i].next){

            int to=edge[i].to;

            if(edge[i].dis+dis[from]>=dis[to]||edge[i].val==edge[i].flow)    continue;

            dis[to]=dis[from]+edge[i].dis;

            pre[to]=i;

            flow[to]=min(flow[from],edge[i].val-edge[i].flow);

            if(!vis[to]){

                vis[to]=;

                q.push(to);

            }

        }

    }

    if(dis[End]==Max)    return ans;

    long long now=End;    ans.val=flow[End];    ans.dis=dis[End];

    sum+=flow[End];

    while(now!=Start){

        long long ret=pre[now];

        edge[ret].flow+=flow[End];

        edge[count(ret)].flow-=flow[End];

        now=edge[ret].from;

    }

    return ans;

}

int main(){

    n=read(),m=read();

    End=calc(n,m,)+;

    for(int i=;i<=n;++i){

        char ch[];

        scanf("%s",ch+);

        for(int j=;j<=m;++j)    sta[i][j]=ch[j]-'';

    }

    for(int i=;i<=n;++i){

        char ch[];

        scanf("%s",ch+);

        for(int j=;j<=m;++j)    edn[i][j]=ch[j]-'';

    }

    for(int i=;i<=n;++i){

        char ch[];

        scanf("%s",ch+);

        for(int j=;j<=m;++j)    swa[i][j]=ch[j]-'';

    }

    int sum1=,sum2=;

    for(int i=;i<=n;++i)

        for(int j=;j<=m;++j){

            if(sta[i][j]){

                sum1++;

                add(Start,calc(i,j,),,);

            }

            if(edn[i][j]){

                sum2++;

                add(calc(i,j,),End,,);

            }

            if(sta[i][j]&&(!edn[i][j])){

                add(calc(i,j,),calc(i,j,),,swa[i][j]>>);

                add(calc(i,j,),calc(i,j,),,(swa[i][j]+)>>);

            }

            if((!sta[i][j])&&edn[i][j]){

                add(calc(i,j,),calc(i,j,),,(swa[i][j]+)>>);

                add(calc(i,j,),calc(i,j,),,swa[i][j]>>);

            }

            if(sta[i][j]==edn[i][j]){

                add(calc(i,j,),calc(i,j,),,swa[i][j]>>);

                add(calc(i,j,),calc(i,j,),,swa[i][j]>>);

            }

            for(int k=;k<;++k){

                int x=i+u[k];int y=j+w[k];

                if(x<||x>n||y<||y>m)    continue;

                add(calc(i,j,),calc(x,y,),,0x7fffffff);

            }

        }

    if(sum1!=sum2){

        printf("-1");

        return ;

    }

    int ans=;

    while(){

        Ans now=spfa();

        if(!now.val)    break;

        ans+=now.val*now.dis;

    }

    if(sum!=sum1){

        printf("-1");

        return ;

    }

    printf("%d",ans);

    return ;

}

https://www.luogu.org/problemnew/solution/P3159