题目概述

有 $n$ 个由双向边连通的城市，$1$ 号城市里住着神犇JZ。$i$ 号城市想要离JZ所在城市距离为 $want_i$ ，如果实际的距离为 $real_i$ ，那么就会有 $(want_i-real_i)^2$ 的不满意度。求任意加边后最小的不满意度。

解题报告

$n$ 这么小……但显然不能DFS和状压DP，所以往网络流的方向想。

显然一个城市只能选择一个 $real$ ，所以和切糕模型一样，把城市按照距离拆点后串起来，边的容量为不满意度。

限制是什么？因为可以任意加边，所以距离不可能比初始距离小，那么就需要把超过初始距离的边的容量改为 $INF$ 。同时原先相邻的两个点距离之差不可能超过 $1​$ ，因此按照切糕模型的套路连边即可。

示例程序

#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=40,maxt=maxn*maxn,maxm=(maxt+(maxt*maxn<<1))<<1,INF=2e9;

class FoxAndCity{
#define ID(x,y) (((x)-1)*n+(y))
#define sqr(x) ((x)*(x))
    int n,E,lnk[maxt+5],son[maxm+5],nxt[maxm+5];
    int que[maxt+5],dis[maxt+5],ti,vis[maxt+5],cur[maxt+5];
    pair<int,int> e[maxm+5];
    inline void Add(int x,int y,int z){
        son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
        son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
    }
    inline bool Bfs(int s,int t){
        int Head=0,Tail=0;que[++Tail]=s;dis[s]=0;vis[s]=++ti;
        while (Head!=Tail)
            for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
                if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,dis[u]=dis[x]+1,vis[u]=ti;
        return vis[t]==ti;
    }
    int Dfs(int x,int t,int MIN=INF){
        if (x==t||!MIN) return MIN;int now,f=0;
        for (int &j=cur[x];~j;j=nxt[j])
            if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],t,min(MIN,e[j].sc-e[j].fr)))){
                e[j].fr+=now;e[j^1].fr-=now;f+=now;
                if (!(MIN-=now)) break;
            }
        return f;
    }
public:
    int minimalCost(vector <string> linked,vector <int> want){
        n=linked[0].size();int S=0,T=n*n+1;E=0;memset(lnk,255,sizeof(lnk));
        int Head=0,Tail=0;que[++Tail]=1;dis[1]=0;vis[1]=++ti;
        while (Head!=Tail)
            for (int x=que[++Head],j=1;j<=n;j++)
                if (vis[j]<ti&&linked[x-1][j-1]=='Y') que[++Tail]=j,dis[j]=dis[x]+1,vis[j]=ti;
        for (int i=2;i<=n;i++){
            Add(S,ID(i,1),sqr(want[i-1]-1));
            for (int j=2;j<=dis[i];j++) Add(ID(i,j-1),ID(i,j),sqr(want[i-1]-j));
            for (int j=dis[i]+1;j<n;j++) Add(ID(i,j-1),ID(i,j),INF);
            Add(ID(i,n-1),T,INF);
        }
        for (int i=2;i<=n;i++)
            for (int j=2;j<=n;j++)
                if (linked[i-1][j-1]=='Y')
                    for (int k=1;k<=n;k++){
                        if (k>2) Add(ID(i,k-1),ID(j,k-2),INF);
                        if (k<n) Add(ID(j,k+1),ID(i,k),INF);
                    }
        int ans=0;while (Bfs(S,T)) memcpy(cur,lnk,sizeof(lnk)),ans+=Dfs(S,T);
        return ans;
    }
};