【泉七培训-杨国烨】图

2014年12月26日1,4200

【题目描述】

给一张联通无向图,定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边,再给定N个A[i],要求添加若干条无向边,使得Σ(a[i] – Dist[1][i])^2最小。输出最小的答案。

【输入格式】

第一行是整数N,表示节点数。

接下来是N*N的矩阵,mat[i][j] = ‘Y’表示i和j之间有一条无向边。保证mat[i][j] = mat[j][i]。

接下来N个数,表示A[i]。

【输出格式】

求答案。

【样例输入】

4

NYNN

YNYN

NYNY

NNYN

0 3 3 3

【样例输出】

5

【样例解释】

不用额外建任何边了233

【数据规模和约定】

对于10%的数据,N<=4。

对于100%的数据,2<=N<=40。

题解

orz cxjyxx_me

最短路满足|Dist[i] – Dist[j]| <= 1,0号节点的Dist一定是0。其他的一定>=1。

因为可以任意添加边,所以任意一组满足上面的条件的dist都是合法的。←自己证明吧,不算难。所以我们现在的问题就是,我们要给每一个节点指定一个dist,满足对于原图的任意一条边,|Dist[i]-Dist[j]|<=1。要求最小化Σ(Dist[i]-A[i])^2。

拆开绝对值,就是Dist[i]-Dist[j]<=1,并且Dist[j]-Dist[i]<=1。每一个限制都可以理解为:如果i取了Dist[i]的话,j至少得取Dist[i]-1以上。

我们用网络流模型来刻画这个东西。

因为dist的取值只有N种,我们对于每个点,拆成N个点。

(i, j) -> (i, j + 1) 容量为(A[i] – j)^2,

对于原图的一条边(u, v)

对于所有的j,

连接(u, j) -> (v, j – 1), (v, j) ->(u, j – 1),容量均为正无穷。

考虑这个图的割,很显然它只可能割在第一种的边上。

因为我们连接了(u, j) ->(v, j – 1),那么很显然如果u这个点割在了(u, j)->(u, j+1)的话,v至少得割一条>=j-1的边才能满足没有增广路。所以构图成立,直接跑最小割即可。

注意特判0号节点的情况。

以前做过的,忘记发出来