题目大意

给定一个无向图，每条边的边权固定为 1，现在你可以自己加一些边权也为 1 的边，最小化
$\sum_{i=1}^n (A_i-dist_i)^2$i=1∑n​(Ai​−disti​)2
其中 $dist_i$disti​ 表示第 i 个点到 1 的最短路长度。

题解

现在我们要最小化 $\sum_{i=1}^m (A_i-dist_i)^2$∑i=1m​(Ai​−disti​)2，因此我们要得到一个可行的$dist$dist的解，由于我们现在要求最短路，因此加边以后对于原来的每条边都要满足松弛条件：$\left|dist_i-dist_j\right|\leq 1$∣disti​−distj​∣≤1，而且 $dist_1=0$dist1​=0，因此实际上我们现在存在一个需要最优化的函数以及一些限定条件，看起来和线性规划很像呢。但其实有问题，因为最优化函数包含平方项，因此：
$z=\sum_{i=1}^n (A_i-x_i)^2 \\ s.t. \begin{cases} \left|x_i-x_j\right|\leq 1(adj(i,j))\\ 0\leq x_i&lt;n\\ x_1=0 \end{cases}$z=i=1∑n​(Ai​−xi​)2s.t.⎩⎪⎨⎪⎧​∣xi​−xj​∣≤1(adj(i,j))0≤xi​<nx1​=0​
是不能直接单纯形的。但是因为这道题的数据范围很小，我们可以修改变量。为了使变量和平方没有关系，我们将 $dist_i$disti​ 拆成 $x_{i,j}=1$xi,j​=1 表示 $dist_i= j$disti​=j，这样我们的规划式变成：
$z=\sum_{i=1}^n \sum_{j=0}^{n-1} x_{i,j}(A_i-j)^2\\ s.t.\begin{cases} \sum_{j=0}^{n-1}x_{i,j}=1(i\in [1,n])\\ x_{1,0}=1\\ 若 x_{i,p}=1,x_{j,q}=1，那么|p-q|\leq 1\\ \end{cases}$z=i=1∑n​j=0∑n−1​xi,j​(Ai​−j)2s.t.⎩⎪⎨⎪⎧​∑j=0n−1​xi,j​=1(i∈[1,n])x1,0​=1若xi,p​=1,xj,q​=1，那么∣p−q∣≤1​
如果我们换一种形式，令 $x_{i,j}=1$xi,j​=1 表示 $dist_i\leq j$disti​≤j，那么式子长得更简单一些
$z=\sum_{i=1}^n \sum_{j=0}^{n-1} (x_{i,j}-x_{i,j-1})(A_i-j)^2\\ s.t.\begin{cases} x_{i,n-1}=1\\ x_{1,0}=1\\ x_{i,p}=0,x_{j,q}=1 不合法(p&gt;q)\\ \end{cases}$z=i=1∑n​j=0∑n−1​(xi,j​−xi,j−1​)(Ai​−j)2s.t.⎩⎪⎨⎪⎧​xi,n−1​=1x1,0​=1xi,p​=0,xj,q​=1不合法(p>q)​
其中对于 $z$z，因为$x_{i,j}=1$xi,j​=1表示$dist_i\leq j$disti​≤j，所以当 $x_{i,j}=1,x_{i,j-1}=0$xi,j​=1,xi,j−1​=0时表示$dist_i=j$disti​=j，所以是 $(x_{i,j}-x_{i,j-1})(A_i-j)^2$(xi,j​−xi,j−1​)(Ai​−j)2 。
第二个判定式的意思是说：$dist_i&gt;q$disti​>q and $dist_j\leq q$distj​≤q的情况不合法。
实际上这种表示方法仍然不方便处理，再转化成最小割的形式：
$\min\left\{\sum \max\{0,x_{i,k}-x_{i,k-1}\}\cdot (A_i-k)^2+ \sum\max\{0,1-x_{i,n-1}\}\cdot \infin+ \sum\max\{0,x_{i,k-1}-x_{j,k}\}\cdot \infin \right\}$min{∑max{0,xi,k​−xi,k−1​}⋅(Ai​−k)2+∑max{0,1−xi,n−1​}⋅∞+∑max{0,xi,k−1​−xj,k​}⋅∞}
表示限制 $x_{i,n-1}=1$xi,n−1​=1，且$i&lt;k$i<k时$j&gt;k$j>k不合法。

构出来的图长这样（没错就是原 wiki 的图，我盗走了），节点 $d_i\leq j$di​≤j 即为我给出的表达式 $x_{i,j}$xi,j​。其中 i 和 j 在原图中有边相连，因此要限制松弛关系，所以两行的节点直接要连边，边权 inf（图中省略了）。同时，因为点 1 的 dist 必为 0，因此 $c(1,j)=\infin (j&gt;0)$c(1,j)=∞(j>0)

（这篇博客是为了解释为什么是 $d_j\leq k$dj​≤k 连向 $d_i\leq k-1$di​≤k−1 而不是反过来连）

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define rep(i,j,k) for(int i=j;i<k;++i)
const int N = 2005, M = 5e6 + 10, inf = 0x3f3f3f3f;
int h[N], p[M], v[M], w[M], edge = 1, s, t;
int level[N], cur[N], vis[N], q[N], a[N];

void add(int a, int b, int c) {
    p[++edge] = h[a]; v[edge] = b; w[edge] = c; h[a] = edge;
    p[++edge] = h[b]; v[edge] = a; w[edge] = 0; h[b] = edge;
}

bool bfs() {
    int i, x, f = 0, r = 0;
    FOR(i,0,t) level[i] = -1;
    q[r++] = s; level[s] = 0;
    while (f < r) {
        x = q[f++];
        for (i = h[x]; i; i = p[i])
            if (w[i] && level[v[i]] == -1) {
                level[v[i]] = level[x] + 1;
                q[r++] = v[i];
            }
    }
    return level[t] != -1;
}

int dfs(int x, int low) {
    int i, tmp, res = 0;
    if (x == t) return low;
    for (i = cur[x]; i && res < low; i = p[i])
        if (w[i] && level[v[i]] == level[x] + 1) {
            tmp = dfs(v[i], min(low - res, w[i]));
            w[i] -= tmp; w[i ^ 1] += tmp; res += tmp;
            if (w[i]) cur[x] = i;
        }
    if (!res) level[x] = -1;
    return res;
}

int dinic() {
    int ans = 0, i;
    while (bfs()) {
        FOR(i,0,t) cur[i] = h[i];
        ans += dfs(s, inf);
    }
    return ans;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        s = n * n; t = n * n + 1;
        FOR(i,0,t) h[i] = 0;
        edge = 1;

        rep(e,0,m) {
            int i, j;
            scanf("%d%d", &i, &j); --i, --j;
            rep(k,1,n) {
                add(i * n + k, j * n + k - 1, inf);
                add(j * n + k, i * n + k - 1, inf);
            }
        }

        rep(i,0,n) scanf("%d", &a[i]);

        rep(k,1,n) {
            add(k - 1, k, inf);
        }
        add(s, 0, a[0] * a[0]);
        add(n - 1, t, inf);

        rep(i,1,n) {
            rep(k,0,n) {
                add(k == 0 ? s : i * n + k - 1,
                    i * n + k,
                    (a[i] - k) * (a[i] - k));
            }
            add(i * n + n - 1, t, inf);
        }

        printf("%d\n", dinic());
    }
}