相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/12/FoxAndCity.html
中文题面：http://paste.ubuntu.com/23693047/
解题报告
这题第一眼看到后觉得绝逼是一个DP
然而是网络流 QwQ
考虑原图，实际上是给定了每个点的距离上限和一些形如 \({dis_i}<={dis_j}+1\) 的关系
再考虑建边,就是更改一个点的 \(dis\)，注意可能会引起一系列点的 \(dis\)的变化
这样的话，套用BZOJ 3144的模型就可以啦！
于是跑一个最小割就好
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 30000;
const int M = 500000;
const int INF = 1e9;
int n,E,S,T,head[N],to[M],nxt[M],flow[M],MX[N];
class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
memcpy(cur, head, sizeof(head));
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;
class FoxAndCity {
int dis[100][100];
public:
int minimalCost(vector<string> linked, vector<int> want) {
init();
n = want.size();
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (linked[i][j] == 'Y') dis[i+1][j+1] = 1;
else dis[i+1][j+1] = INF;
}
}
Floyd();
for (int i=2;i<=n;i++)
MX[i] = dis[1][i];
init(); S = 0; T = N - 1;
for (int i=2;i<=n;i++) {
Add_Edge(S, id(i, 1));
Add_Edge(id(i, MX[i]+1), T);
for (int j=1;j<=MX[i];j++) {
Add_Edge(id(i,j), id(i,j+1), sqr(want[i-1]-j));
for (int k=2;k<=n;k++) {
if (i != k && dis[i][k] == 1 && j > 1) {
Add_Edge(id(i, j), id(k, j-1));
}
}
}
}
return Dinic.MaxFlow();
}
private:
inline void init() {
E = 1;
memset(head,0,sizeof(head));
}
inline int id(int x, int y) {
return (x-1) * (n+1) + y;
}
inline int sqr(int w) {
return w * w;
}
inline void Add_Edge(int u, int v, int f = INF) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}
inline void Floyd() {
for (int k=1;k<=n;k++) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
};
