题目地址：TopCoder Arena：Practice – TopCoder Arena、vjudge：CurvyonRails – TopCoder 12432 – Virtual Judge

题目描述

Cat Carol is the queen of Gridland. Gridland is a rectangular country divided into a grid of unit square cells. Each cell contains either a town or a wasteland. Carol has decided to construct some railroad tracks according to the following rules:

• The cells with wasteland must not contain any railroad tracks.
• Each town cell has to contain a single segment of railroad tracks that connects two of its four sides.
• Each segment of tracks has to be connected to two other segments of tracks (one on each end).

Note that Carol does not require the entire set of tracks to be connected. Configurations that consist of multiple disjoint loops are acceptable, too.
A Curvy is a curious animal indigenous to Gridland. These animals love curves and hate straight things. Some of the towns in Gridland are inhabited by Curvies. If such a town happens to contain a straight segment of tracks (i.e., a segment that connects two opposite sides of the cell), the Curvies in the town are very unhappy.
You are given a String[] field that describes Gridland: each character of each element of field describes one of its cells. The meaning of individual characters follows.

• The character ‘.’ represents a town without Curvies.
• The character ‘C’ represents a town with Curvies.
• The character ‘w’ represents a wasteland.

Compute and return the minimal number of towns with unhappy Curvies when the railroad tracks are constructed according to the above constraints. If there is no way to construct the railroads according to the given rules, return -1 instead.
要求在一个方格图上修建火车轨道，使得轨道都能构成自环。注意有一些格子有障碍，还有些格子在放置直轨道的时候产生费用。

定义名

类名：CurvyonRails
函数名：getmin
参数：vector <string>
返回值：int
函数声明：int getmin(vector <string> field)

样例

样例#1：

..
..

样例#1结果：

0

其他样例参见原网站。

说明

• field will contain between 1 and 25 elements, inclusive.
• Each element of field will contain between 1 and 25 characters, inclusive.
• Each element of field will contain the same number of characters.
• Each character of each element of field will be ‘.’, ‘w’ or ‘C’.

题解

参考资料：Topcoder SRM570 900 CurvyonRails – Enigma_aw – 博客园
如果把方格图抽象成普通图，一条轨道会使一个格子产生2的度数。我们考虑对这个方格图黑白染色，以便控制度数/流量平衡的条件，即度数为2。在这里不使用拆点的方法是因为图是无向图，不需要区分出度与入度。
我们可以建立一个源→黑点→白点→汇的网络，其中，所有的边都设置成容量2的边，用于限制度数。但是这样的图显然是不能够符合要求的，因为我们还要区分直轨弯轨与费用问题。对于直轨弯轨，我们发现直轨只产生横向或纵向的2个度数，而弯轨产生的度数是横纵各1的。我们对一个点拆成横向度数和纵向度数两个点，在黑白点的连接时也区分横纵度数连边即可。我们再用一个总点来限流，即现在的网络变为了源→黑点→黑点的横/纵点→白点的横/纵点→白点→汇，其中源→黑点→黑点的横/纵点之间的边都为容量2的边（白点类似）。至于费用问题，由于我们已经区分了横纵点，对于直轨会产生费用的点，我们从总点向横/纵点建边时建一条容量1费用0的边，再建一条容量1费用1的边，就可以表示如果同一方向产生2个度数产生的费用了。
网络上跑最小费用最大流即可，如果不能满流，说明无解。

代码

由于TopCoder要求实现一个class，下面的代码并不是标准输入/输出格式（传统OI题目）的实现方式，但是把调试注释给去掉就可以用标准输入/输出了。

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

#include <iostream>
#include <vector>
#include <string>
#include <queue>

const int MAXN = 100005, INF = 1e9;

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

inline void reset() {
    memset(head, -1, sizeof(head)); tot = 0;
}

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));
    que.push(s); inque[s] = true; f[s] = INF; dis[s] = 0;
    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(f[u], gra[i].cap);
                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)) {
        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];
        }
    }
}

int n, m, S, T;

class CurvyonRails {
public:
    inline int getmin(std::vector<std::string> field) {
        n = field.size(); m = field[0].size();
        S = n * m * 3 + 1; T = S + 1;
        reset();
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                int ii = i - 1, jj = j - 1;
                if(field[ii][jj] == 'w') continue;
                if(!((i + j) & 1)) {
                    sum += 2;
                    addedge(S, (i - 1) * m + j, 2, 0);
                    if(field[ii][jj] != 'C') {
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m, 2, 0);
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m * 2, 2, 0);
                    } else {
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m, 1, 0);
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m * 2, 1, 0);
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m, 1, 1);
                        addedge((i - 1) * m + j, (i - 1) * m + j + n * m * 2, 1, 1);
                    }
                    if(j - 1 >= 1 && field[ii][jj - 1] != 'w') {
                        addedge((i - 1) * m + j + n * m, (i - 1) * m + j - 1 + n * m, 1, 0);
                    }
                    if(j + 1 <= m && field[ii][jj + 1] != 'w') {
                        addedge((i - 1) * m + j + n * m, (i - 1) * m + j + 1 + n * m, 1, 0);
                    }
                    if(i - 1 >= 1 && field[ii - 1][jj] != 'w') {
                        addedge((i - 1) * m + j + n * m * 2, 
                            (i - 2) * m + j + n * m * 2, 1, 0);
                    }
                    if(i + 1 <= n && field[ii + 1][jj] != 'w') {
                        addedge((i - 1) * m + j + n * m * 2, i * m + j + n * m * 2, 1, 0);
                    }
                } else {
                    addedge((i - 1) * m + j, T, 2, 0);
                    if(field[ii][jj] != 'C') {
                        addedge((i - 1) * m + j + n * m, (i - 1) * m + j, 2, 0);
                        addedge((i - 1) * m + j + n * m * 2, (i - 1) * m + j, 2, 0);
                    } else {
                        addedge((i - 1) * m + j + n * m, (i - 1) * m + j, 1, 0);
                        addedge((i - 1) * m + j + n * m * 2, (i - 1) * m + j, 1, 0);
                        addedge((i - 1) * m + j + n * m, (i - 1) * m + j, 1, 1);
                        addedge((i - 1) * m + j + n * m * 2, (i - 1) * m + j, 1, 1);
                    }
                }
            }
        }
        mcmf(S, T);
        if(flow < sum) {
            return -1;
        } else {
            return cost;
        }
    }
};

/*int main() {
    std::string t;
    std::vector<std::string> field;
    while(!getline(std::cin, t).eof()) {
        field.push_back(t);
    }
    CurvyonRails solver;
    printf("%d", solver.getmin(field));
    return 0;
}*/