题目地址：洛谷：【P3159】[CQOI2012]交换棋子 – 洛谷、BZOJ：Problem 2668. — [cqoi2012]交换棋子

题目描述

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

输入输出格式

输入格式：
第一行包含两个整数n，m（1<=n, m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。

输出格式：
输出仅一行，为最小交换总次数。如果无解，输出-1。

输入输出样例

输入样例#1：

3 3
110
000
001
000
110
100
222
222
222

输出样例#1：

4

题解

如果我们把棋盘上看做只有黑色棋子，那么可以把交换达到目标状态看做把每个黑色棋子移动到目标位置上去。在移动的过程中，起终点格子各参与一次交换，路径上的其他格子各参与两次交换。既然如此，我们可以把次数上限平分成向上一步交换和向下一步交换两部分。
建图的时候，把每个格子拆成三个点，入点、原点、出点，流的方向应该是入点→原点→出点，这三个点之间的边，容量均为次数上限的一半，不妨把交换次数（费用）放在入点→原点的边上，可以避免算多交换次数。
对于初始状态的黑点格子，从源向该格子的原点连容量1费用0的边，对于目标状态的黑点格子，从该格子的原点向汇连容量1费用0的边，对于有公共点/边的格子，从出点向入点连容量无限费用0的边。至此网络就建立完成了，只需要跑最小费用最大流，若满流则答案为费用，否则无解。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int readdigit() {
    char c;
    while(!isdigit(c = fgc())) {}
    return c - '0';
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(f[u], gra[i].cap);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    que.push(v); inque[v] = true;
                }
            }
        }
    }
    return f[t];
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        flow += f[t]; cost += f[t] * dis[t];
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t]; gra[pree[i] ^ 1].cap += f[t];
        }
    }
}

const int fix[][8] = {{-1, 1, -1, 1, -1, 1, 0, 0}, {0, 0, -1, 1, 1, -1, -1, 1}};

int n, m, cnt, st[25][25], ed[25][25], lim[25][25], S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); S = n * m * 3 + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            st[i][j] = readdigit();
            if(st[i][j]) cnt++;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ed[i][j] = readdigit();
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            lim[i][j] = readdigit();
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(st[i][j]) addedge(S, (i - 1) * m + j, 1, 0);
            if(ed[i][j]) addedge((i - 1) * m + j, T, 1, 0);
            if(st[i][j] && !ed[i][j]) {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, (lim[i][j] + 1) / 2, 0);
            } else if(!st[i][j] && ed[i][j]) {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, (lim[i][j] + 1) / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
            } else {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
            }
            for(int k = 0; k < 8; k++) {
                int nx = i + fix[0][k], ny = j + fix[1][k];
                if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                addedge(n * m * 2 + (i - 1) * m + j, n * m + (nx - 1) * m + ny, INF, 0);
            }
        }
    }
    mcmf(S, T);
    printf("%d", flow >= cnt ? cost : -1);
    return 0;
}

题目地址：洛谷：【P2153】[SDOI2009]晨跑 – 洛谷、BZOJ：Problem 1877. — [SDOI2009]晨跑

题目描述

Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以 在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
存在 1→n 的边存在。这种情况下，这条边只能走一次。

输入输出格式

输入格式：
第一行：两个数N,M。表示十字路口数和街道数。 接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。

输出格式：
两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长 度。

输入输出样例

输入样例#1：

7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1

输出样例#1：

2 11

说明

对于30%的数据，N ≤ 20，M ≤ 120。
对于100%的数据，N ≤ 200，M ≤ 20000。

题解

打个MCMF板子练练手。
最小费用最大流的裸题，对每个点拆点限制流量为1即可，天数就是最大流，路程长度就是费用。注意1和n两个点不能拆点，加边的时候特判一下。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int n, m;

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(gra[i].cap, f[u]);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return f[t] != 0;
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t]; cost += dis[t] * f[t];
    }
}

int a, b, c;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    for(int i = 2; i < n; i++) {
        addedge(i, i + n, 1, 0);
    }
    for(int i = 1; i <= m; i++) {
        a = readint(); b = readint(); c = readint();
        if(a == 1) addedge(1, b, 1, c);
        else addedge(a + n, b, 1, c);
    }
    mcmf(1, n);
    printf("%d %d", flow, cost);
    return 0;
}