可以看成给每个点随便选权值，有相邻边的点权值相差不超过 1 <script type="math/tex" id="MathJax-Element-25">1</script>。因为原图是联通的，每种满足要求的方案都一定是合法的。这样建图跑最小割就行了，参见【HNOI2013】bzoj3144 切糕。
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
const int maxn=200010,s=20005,t=20006,oo=0x3f3f3f3f;
class FoxAndCity
{int fir[maxn],ne[maxn],to[maxn],w[maxn],que[maxn],dep[maxn],cur[maxn],id[45][45],n,num,tot;
private:void add(int u,int v,int x){num++;ne[num<<1]=fir[u];fir[u]=num<<1;to[num<<1]=v;w[num<<1]=x;ne[num<<1|1]=fir[v];fir[v]=num<<1|1;to[num<<1|1]=u;w[num<<1|1]=0;}int bfs(){int hd=1,tl=1,u,v;for (int i=1;i<=tot;i++) dep[i]=0;dep[t]=0;que[dep[s]=1]=s;while (hd<=tl){u=que[hd++];cur[u]=fir[u];for (int i=fir[u];i;i=ne[i])if (w[i]&&!dep[v=to[i]]){dep[v]=dep[u]+1;que[++tl]=v;}}return dep[t];}int dfs(int u,int lim){if (u==t) return lim;int ret=0,v,x;for (int &i=cur[u];i&&ret<lim;i=ne[i])if (w[i]&&dep[v=to[i]]==dep[u]+1){x=dfs(v,min(w[i],lim-ret));ret+=x;w[i]-=x;w[i^1]+=x;}return ret;}
public:int minimalCost(vector<string> linked,vector<int> want){int ans=0;n=want.size();tot=num=0;for (int i=0;i<n;i++)for (int j=0;j<=n;j++)id[i][j]=++tot;for (int i=1;i<=tot;i++) fir[i]=0;fir[s]=fir[t]=0;add(s,id[0][0],oo);add(id[0][n],t,oo);for (int i=1;i<n;i++) add(id[0][i],id[0][i+1],oo);for (int i=1;i<n;i++){add(s,id[i][0],oo);add(id[i][0],id[i][1],oo);add(id[i][n],t,oo);for (int j=want[i]-1;j>=1;j--)add(id[i][j],id[i][j+1],(want[i]-j)*(want[i]-j));for (int j=want[i]+1;j<n;j++)add(id[i][j],id[i][j+1],(j-want[i])*(j-want[i]));}for (int i=0;i<n;i++)for (int j=i+1;j<n;j++)if (linked[i][j]=='Y')for (int k=0;k<n;k++){add(id[i][k+1],id[j][k],oo);add(id[j][k+1],id[i][k],oo);}while (bfs()) ans+=dfs(s,oo);return ans;}
};