[CQOI2012] 交换棋子

有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。

Solution

一个点拆三份，入点，主点，出点

入点向主点连边，主点向出点连边，设该点允许的交换次数为 \(x\) ，根据以下规则确定

若为初态点，则入边限流 \(x/2\)，出边限流 \((x+1)/2\)
若为末态点，则入边限流 \((x+1)/2\)，出边限流 \(x/2\)
否则，入边限流 \(x/2\)，出边限流 \((x+1)/2\)

\(S \to\) 初态点，末态点 \(\to T\)，容量 \(1\)，费用 \(0\)

八连通相互连边，容量 \(\infty\)，费用 \(1\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define ll long long

#define reset(x) memset(x,0,sizeof x)

#define reset3f(x) memset(x,0x3f,sizeof x)

const int N = 1005;

namespace flow {

const int N = 100005;

const int M = 1000005;

const int inf = 1e+12;

struct Edge {

    int p, c, w, nxt = -1;

} e[N];

int s, t, tans, ans, cost, ind, bus[N], qhead = 0, qtail = -1, qu[M],vis[N], dist[N];

void graph_link(int p, int q, int c, int w) {

    e[ind].p = q;

    e[ind].c = c;

    e[ind].w = w;

    e[ind].nxt = bus[p];

    bus[p] = ind;

    ++ind;

}

void make(int p, int q, int c, int w) {

    graph_link(p, q, c, w);

    graph_link(q, p, 0, -w);

}

int dinic_spfa() {

    qhead = 0;

    qtail = -1;

    memset(vis, 0x00, sizeof vis);

    memset(dist, 0x3f, sizeof dist);

    vis[s] = 1;

    dist[s] = 0;

    qu[++qtail] = s;

    while (qtail >= qhead) {

        int p = qu[qhead++];

        vis[p] = 0;

        for (int i = bus[p]; i != -1; i = e[i].nxt)

            if (dist[e[i].p] > dist[p] + e[i].w && e[i].c > 0) {

                dist[e[i].p] = dist[p] + e[i].w;

                if (vis[e[i].p] == 0)

                    vis[e[i].p] = 1, qu[++qtail] = e[i].p;

            }

    }

    return dist[t] < inf;

}

int dinic_dfs(int p, int lim) {

    if (p == t)

        return lim;

    vis[p] = 1;

    int ret = 0;

    for (int i = bus[p]; i != -1; i = e[i].nxt) {

        int q = e[i].p;

        if (e[i].c > 0 && dist[q] == dist[p] + e[i].w && vis[q] == 0) {

            int res = dinic_dfs(q, min(lim, e[i].c));

            cost += res * e[i].w;

            e[i].c -= res;

            e[i ^ 1].c += res;

            ret += res;

            lim -= res;

            if (lim == 0)

                break;

        }

    }

    return ret;

}

void solve(int _s,int _t) {

    s=_s; t=_t;

    while (dinic_spfa()) {

        memset(vis, 0x00, sizeof vis);

        ans += dinic_dfs(s, inf);

    }

}

void init() {

    memset(bus, 0xff, sizeof bus);

}

}

int n,m;

char a[N][N],b[N][N],c[N][N];

int idIn(int i,int j) {

    return i*m-m+j+2;

}

int idMid(int i,int j) {

    return 2ll + n*m + i*m-m+j;

}

int idOut(int i,int j) {

    return 2ll + 2*n*m + i*m-m+j;

}

int check(int i,int j) {

    if(i && j && i<=n && j<=m) return 1;

    return 0;

}

signed main() {

    flow::init();

	cin>>n>>m;

	for(int i=1;i<=n;i++) cin>>a[i]+1;

	for(int i=1;i<=n;i++) cin>>b[i]+1;

	for(int i=1;i<=n;i++) cin>>c[i]+1;

	int cnt=0,tot=0;

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

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

            if(a[i][j]=='1') cnt++;

            if(b[i][j]=='1') tot++;

        }

	}

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

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

            if(a[i][j]=='1') flow::make(1,idMid(i,j),1,0);

            if(b[i][j]=='1') flow::make(idMid(i,j),2,1,0);

            int x=c[i][j]-'0';

            if(a[i][j]=='1' && b[i][j]=='0') {

                flow::make(idIn(i,j),idMid(i,j),x/2,0);

                flow::make(idMid(i,j),idOut(i,j),(x+1)/2,0);

            }

            else if(a[i][j]=='0' && b[i][j]=='1') {

                flow::make(idIn(i,j),idMid(i,j),(x+1)/2,0);

                flow::make(idMid(i,j),idOut(i,j),x/2,0);

            }

            else {

                flow::make(idIn(i,j),idMid(i,j),x/2,0);

                flow::make(idMid(i,j),idOut(i,j),(x+1)/2,0);

            }

            for(int k=i-1;k<=i+1;k++) {

                for(int l=j-1;l<=j+1;l++) {

                    if(i!=k || j!=l) {

                        if(check(k,l)) flow::make(idOut(i,j),idIn(k,l),99,1);

                    }

                }

            }

        }

    }

    flow::solve(1,2);

    if(flow::ans==cnt && cnt==tot) cout<<flow::cost;

    else cout<<-1;

}

巴特西

[CQOI2012] 交换棋子 - 费用流

Solution

最新文章

热门文章