Link
注意到原图给的是一个无向连通图。
如果在原图中两点之间有一条无向边，那么这两点到(1)的距离之差不大于(1)。
这个命题的正确性是显然的，我们考虑它的逆命题：
给定每个点到(1)的距离（不大于(n)），并给定一些已有的边，满足已有的边的两端到(1)的距离之差不大于(1)，那么一定存在一种方案满足该种情况。
因为题目给的是一个无向连通图，所以我们可以先构造一条最短路径递增的链，然后再把其它的点挂在上面即可。
那么现在就变成了距离限制模型，直接最小割即可。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
int read(){int x;scanf("%d",&x);return x;}
const int N=47,V=2007,E=150007,inf=1e9;
int n,s,t,tot=1,e[N][N],w[N],head[V],ver[E],next[E],edge[E],cur[V],dep[V];std::queue<int>q;
int sqr(int a){return a*a;}
void add(int u,int v,int w){ver[++tot]=v,next[tot]=head[u],edge[tot]=w,head[u]=tot,ver[++tot]=u,next[tot]=head[v],edge[tot]=0,head[v]=tot;}
int bfs()
{
memset(dep+1,0x3f,t<<2),memcpy(cur+1,head+1,t<<2),dep[s]=0,q.push(s);
for(int i,u,v;!q.empty();) for(u=q.front(),q.pop(),i=head[u];i;i=next[i]) if(dep[v=ver[i]]>inf&&edge[i]) dep[v]=dep[u]+1,q.push(v);
return dep[t]<inf;
}
int dfs(int u,int lim)
{
if(!lim||u==t) return lim;
int v,flow=0;
for(int&i=cur[u],f;i;i=next[i])
if(dep[v=ver[i]]==dep[u]+1&&(f=dfs(v,std::min(lim,edge[i]))))
{
flow+=f,lim-=f,edge[i]-=f,edge[i^1]+=f;
if(!lim) break;
}
return flow;
}
int dinic(){int ans=0;while(bfs()) ans+=dfs(s,inf);return ans;}
int solve()
{
s=n*n+1,t=s+1;
for(int i=1;i<=n;++i)
{
add(s,(i-1)*n+1,i==1? 0:inf),add(i*n,t,inf);
for(int j=1;j<n;++j) add((i-1)*n+j,(i-1)*n+j+1,i==1? inf:sqr(w[i]-j));
for(int j=1;j<=n;++j) if(e[i][j]) for(int k=1;k<n;++k) add((i-1)*n+k+1,(j-1)*n+k,inf);
}
return dinic();
}
class FoxAndCity
{
public:
int minimalCost(std::vector<std::string>g,std::vector<int>vec)
{
n=g.size();
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) e[i][j]=g[i-1][j-1]=='Y';
for(int i=1;i<=n;++i) w[i]=vec[i-1];
return solve();
}
};