相关链接
题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=12432
中文题面：http://www.cnblogs.com/enigma-aw/p/6237246.html
神犇题解：http://metthesoul.blog.163.com/blog/static/23032003620147269343401/
解题报告
首先考虑一个简单的子问题：
给定你一个网格图，其中有一些点有障碍，不能经过
问：能否通过一些回路，使得每一个点恰好经过一次
考虑回路的性质：
- 回路中的每一个点的度一定是 $ 2$
- 如果每一个点的度都是 $ 2$ ，那么这一定是由一些回路构成的图
这样的话，这个 $ Subcase$ 就可以通过染色后二分图匹配来解决了
现在回到原问题，显然可行解的判断可以用上述算法来解决
现在来考虑 towns with Curvies
在上一个 $ Subcase$ 中使用的二分图匹配，实际上是对 度 进行匹配
现在考虑将度分类：
- 横向的度
- 纵向的度
对于 towns with Curvies 来说：如果同类的度匹配，那么就得付出代价
于是考虑将每一个点拆成一个横向的度和纵向的度
然后原图中相邻的格子，只连对应的点（纵向相邻就只连代表纵向的点）
这样的话，如果存在完备匹配，那么一定是一个两个不同类的度匹配
现在再来考虑付出代价的情况：
将二分图匹配改造成费用流，已建的边费用全部为 $ 0$
然后在同一个格子拆开的点之间连一条双向、流量为 $ 1$、费用为 $ 0$ 的边
这样的话，就相当于两个匹配都使用同一类度的时候得付出 $ 1$ 的代价
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 30;
const int N = 2000;
const int M = 50000;
const int INF = 1000000000;
int S,T,head[N],nxt[M],to[M],flow[M],cost[M];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline pair<int,int> MaxFlow() {
int ret_cost = 0, ret_flow = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
ret_flow += f;
}
return make_pair(ret_cost, ret_flow);
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;
class CurvyonRails {
int n,m,cnt,E;
char pat[L][L];
public:
int getmin(vector<string> field) {
init();
m = field.size();
n = field[0].size();
for (int j=0;j<m;j++) {
for (int i=0;i<n;i++) {
pat[i+1][j+1] = field[j][i];
}
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (pat[i][j] == 'w') continue;
else {
if (++cnt, i + j & 1) {
Add_Edge(id(i,j,0), T, 1);
Add_Edge(id(i,j,1), T, 1);
} else {
Add_Edge(S, id(i,j,0), 1);
Add_Edge(S, id(i,j,1), 1);
for (int k=1,x,y;k<=4;k++) {
x = i + dx[k];
y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= m) {
if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1);
if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1);
}
}
}
if (pat[i][j] == '.') {
Add_Edge(id(i,j,0), id(i,j,1), 1);
Add_Edge(id(i,j,1), id(i,j,0), 1);
}
if (pat[i][j] == 'C') {
Add_Edge(id(i,j,0), id(i,j,1), 1, 1);
Add_Edge(id(i,j,1), id(i,j,0), 1, 1);
}
}
}
}
pair<int,int> vout = MCMF.MaxFlow();
if (vout.second < cnt) return -1;
else return vout.first;
}
private:
inline int id(int x, int y, int t) {
return ((y-1)*n + (x-1)) * 2 + 1 + t;
}
inline void init() {
E = 1; S = cnt = 0; T = N - 1;
memset(head,0,sizeof(head));
}
inline void Add_Edge(int u, int v, int f, int c = 0) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}
};
