ACM-ICPC 2017 Asia Xi'an

Problem A

Unsolved.

Problem B

Solved by dreamcloud.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Xiejiadong && dreamcloud && oxx1108.

题意：在图上任意的添加边权为$1$，使得$\sum (a[i]-dist[i])$最小。

题解：建图，最小割。

设源点为$S$，汇点为$T$。

对于原图中每个点$u$，设其在原图中与$1$的距离为$dist[u]$。在新图中，$u$被拆为$u_0,u_1,$…$,u_{dist[u]}$。$ui$向$u_{i+1}$连一条容量为$(A[u]−(i+1))^2$的边，$udist[u]$向$T$连一条容量为无穷的边。如果$u$不是$1$，则$S$向$u_0$连一条无穷的边，否则连一条容量为$(A[1]−0)^2$的边。

对于原图中的每条无向边$(u,v)$，在新图中连若干条形如$(u_i,v_{i−1})$和$(v_i,u_{i−1})$的容量为无穷的有向边。

新图上的一个割对应了一个满足三角不等式的图，流量为该种方案的代价，因此在新图上跑个最大流即可。

Problem F

Unsolved.

Problem G

Solved by Xiejiadong.

Problem H

Solved by dreamcloud.

Problem I

Unsolved.

Problem J

Solved by oxx1108.

Problem K

Solved by dreamcloud.