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

题目描述

There is a country with n cities, numbered 0 through n-1. City 0 is the capital. The road network in the country forms an undirected connected graph. In other words: Some pairs of cities are connected by bidirectional roads.
For every city there is at least one sequence of consecutive roads that leads from the city to the capital. (Whenever two roads need to cross outside of a city, the crossing is done using a bridge, so there are no intersections outside of the cities.)
You are given a linked that describes the road network. For each i and j, linked[i][j] is ‘Y’ if the cities i and j are already connected by a direct road, and it is ‘N’ otherwise.
The distance between two cities is the smallest number of roads one needs to travel to get from one city to the other. The people living outside of the capital are usually unhappy about their distance from the capital. You are also given a want with n elements. For each i, want[i] is the desired distance between city i and the capital (city 0).
Fox Ciel is in charge of building new roads. Each new road must again be bidirectional and connect two cities. Once the new roads are built, the citizens will evaluate how unhappy they are with the resulting road network:
For each i: Let real[i] be the new distance between city i and the capital. Then the people in city i increase the unhappiness of the country by (want[i] – real[i])^2.
Return the minimal total unhappiness Ciel can achieve by building some (possibly zero) new roads.
给定一个n个点的图，你现在可以往图上加边，每个点有个值want[i]，加边后每个点到0的最短路为real[i]，要求最小化\sum_{i=0}^{n-1} (want[i] - real[i])^2。

定义名

类名：FoxAndCity
函数名：minimalCost
参数：vector <string>, vector <int>
返回值：int
函数声明：int minimalCost(vector <string> linked, vector <int> want)

样例

样例#1：

{"NYN", "YNY", "NYN"}
{0, 1, 1}

样例#1结果：

0

其他样例参见原网站。

说明

• n will be between 2 and 40, inclusive.
• linked will contain exactly n elements.
• Each element of linked will contain exactly n characters.
• Each character in linked will be ‘Y’ or ‘N’.
• For each i and j, linked[i][j] = linked[j][i].
• For each i, linked[i][i] = ‘N’.
• The graph described by linked will be connected.
• want will contain exactly n elements.
• Each element in want will be between 0 and n-1, inclusive.
• want[0] will be 0.

题解

参考资料：[最小割] SRM 590 div1 FoxAndCity – CSDN博客
我们考虑有以下性质：

1. real[0] = 0且real[i] \neq 0 \ (i \neq 0)
2. 如果有边 (u, v) \in E，则 |real[u] - real[v]| \leq 1

因此我们可以建立最小割模型，类似[HNOI2013]切糕 题解 | KSkun’s Blog，对每个点的n-1种real[i]取值（0, 1, …, n-1）建点连成链，设置每个点对应的边的容量为选择该real[i]对答案的贡献，其中源→(i, real[i]=0)的点容量无限，因为要满足性质1。对于原图中有边相连的点(u, v)，我们建边(u, real[u]=k)→(v, real[v]=k-1)表示性质2的限制。
注意0点的real只能取0，因此我们的源→(0, real[0]=0)边容量为0，可以选择不建。但是要建(0, real[0]=0)→T的边，容量无限，用于限制与0有边相连的点的real值。

代码

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

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

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

const int MAXN = 1000005, INF = 1e9;

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

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

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

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                flow += d; left -= d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(!left) return flow;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int n, S, T;

class FoxAndCity {
public:
    inline int minimalCost(std::vector<std::string> linked, std::vector<int> want) {
        n = linked.size();
        S = n * n + 1; T = S + 1;
        reset();
        addedge(1, T, INF);
        for(int i = 2; i <= n; i++) {
            addedge(S, (i - 1) * n + 1, INF);
            for(int j = 1; j < n; j++) {
                addedge((i - 1) * n + j, (i - 1) * n + j + 1, 
                    (j - want[i - 1]) * (j - want[i - 1]));
            }
            addedge((i - 1) * n + n, T, INF);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(linked[i - 1][j - 1] == 'Y') {
                    for(int k = 1; k < n; k++) {
                        addedge((i - 1) * n + k + 1, (j - 1) * n + k, INF);
                    }
                }
            }
        }
        return dinic(S, T);
    }
};

/*int main() {
    FoxAndCity solver;
    printf("%d", solver.minimalCost({"NYNNNY", "YNYNNN", "NYNYNN", "NNYNYN", 
        "NNNYNY", "YNNNYN"}, {0, 2, 2, 2, 2, 2}));
    return 0;
}*/