相关链接
题目传送门：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]);
}
}
}
}
};
Aw, this was an extremely good post. Finding the time and actual
effort to generate a great article… but what can I say… I hesitate a whole lot and
don’t seem to get anything done.
Wonderful article! We are linking to this great article on our website.
Keep up the good writing.
Greetings! This is my 1st comment here so I just wanted to give a quick shout out and tell you
I genuinely enjoy reading through your blog posts.
Can you suggest any other blogs/websites/forums that deal with
the same subjects? Thanks a lot!
I like the helpful information you provide in your articles.
I’ll bookmark your blog and check again here regularly.
I’m quite sure I will learn lots of new stuff right here!
Best of luck for the next!
Its like you read my mind! You seem to know so much
approximately this, like you wrote the e-book in it or something.
I believe that you just can do with some percent
to drive the message home a little bit, however instead of that,
that is magnificent blog. A fantastic read.
I’ll certainly be back.
I seriously love your blog.. Great colors & theme.
Did you develop this web site yourself? Please reply back
as I’m hoping to create my own website and would like to find out where you got this
from or just what the theme is named. Cheers!
I every time used to read piece of writing in news
papers but now as I am a user of net so from now I am using net for posts, thanks to web.
Good post! We will be linking to this great article on our website.
Keep up the great writing.
What’s up Dear, are you genuinely visiting this web site regularly, if so after that you will absolutely get pleasant knowledge.
I will immediately grab your rss as I can not find your email subscription link or e-newsletter service.
Do you have any? Kindly permit me know so that I may
just subscribe. Thanks.
Spot on with this write-up, I actually believe this website needs far more attention. I’ll probably be returning to read through more, thanks for the advice!
Hello my loved one! I wish to say that this article is amazing, nice written and include approximately all significant infos.
I’d like to see more posts like this .
certainly like your web-site however you
have to take a look at the spelling on quite a few of your posts.
Many of them are rife with spelling problems and I find it very bothersome to tell the truth however I
will surely come back again.
I really appreciate this post. I?¦ve been looking everywhere for this! Thank goodness I found it on Bing. You’ve made my day! Thx again
Hi there I am so glad I found your weblog, I
really found you by error, while I was browsing
on Aol for something else, Anyhow I am here now and
would just like to say thanks a lot for a remarkable post and a all round entertaining blog (I also love the theme/design), I don’t have
time to look over it all at the moment but I have book-marked it and
also added in your RSS feeds, so when I have time I will be back to read more, Please do keep
up the awesome jo.
Very great post. I simply stumbled upon your weblog and wanted to say that I’ve truly loved browsing your blog posts.
In any case I’ll be subscribing on your rss feed and I hope you write
again very soon!
My partner and I stumbled over here different web address and
thought I may as well check things out. I like what I see
so i am just following you. Look forward to looking into your web page yet
again.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you!
By the way, how could we communicate?
This paragraph presents clear idea designed for the new users
of blogging, that actually how to do blogging and site-building.
It is the best time to make some plans for the longer term
and it’s time to be happy. I have read this publish
and if I could I wish to suggest you some fascinating issues
or suggestions. Maybe you could write subsequent articles referring to this article.
I want to read more issues approximately it!
I real pleased to find this web site on bing, just what I was searching for : D too bookmarked.
Hello, its fastidious paragraph regarding media print, we all be aware of media is a impressive
source of data.