AGC036D Negative Cycle

AGC036D

有个大小为$n$的有向图，其中有$n?1$条不可以删的边，连着$(i,i+1)$。

对于任意$(x,y),x?=y$，都有这样的边：如果$x<y$，那么$(x,y)$连一条$?1$的边。如果$x>y$，那么$(x,y)$连一条$1$的边。

这些都是可以删的边，每条边都有个删除的代价。

现在要删除代价和尽量少的边，使得图中不存在负环。

蛤蛤听说正解是差分约束？。。。

讲讲我想了一天的毒瘤做法。

首先有个出现负环的充要条件：对于一条正边$(u,v)$，若有一条负边$(x,y)$，满足$v\le x\le y\le u$，那么区间$[v,x]$和$[y,u]$缩成一个点（意味着可以以$0$的代价互相到达）。一直缩到不能再缩为止。此时出现负环，当且仅当存在一个点有负自环。

这还挺容易证明的。尽管我第一天晚上看题第二天中午才发现了这条性质。

考虑保留尽量边权和尽量大的边。我们考虑下最优解长成什么样子：

1. 如果一条正边$(u,v)$在答案中，那么正边$(u,w)(w>v)$一定出现在答案中。

   如果一条负边$(x,y)$在答案中，那么负边$(z,y)(z<x)$一定出现在答案中。

   前缀和、后缀和一下，那么对于每个右端点只需要考虑以它为右端点的正边和负边。

2. 在上面这条性质的条件下（意味着每个右端点只需要考虑一条正边和一条负边）。

   一定不存在两条正边（或负边）的区间互相包含。所以随着右端点递增，左端点也跟着递增。

3. 考虑如下的局部结构：

红色的那一片为缩成一个点的区域。

由于希望它最优，所以两段红色区域中，左边区域中每个点到右边区域中每个点都有边（不管是正边还是负边）。推广：对于任意两个缩成一个点的区域，它们之间若有边，那么实际上内部的点都是互相有边。

（这个局部结构可以推广：定义当$k=j?1$时，表示$[j,i]$之间没有负边。这时候就不存在这个红色区域。但在下面DP转移的时候，可以发现实际上可以用同一条式子。）

于是实际上长这样：

(不存在某个右端点没有连正边的，如果没有连，连一下不亏。)

4. 然后还可以证明右边的那段红色区域的左端点为$k+1$：如果左端点大于$k+1$，考虑$k$和左端点之间的某个点。考虑以它为右端点时正边连向哪里，由于上面的第2条性质，一定会连到$j$或之前的某个点。如果连到$j$，不如和右边那段区域缩在一起；如果连到$j$之前，那么一定不会在$k$连向的左端点的左边。结合第3条性质的那个图，连向的位置和$k$连向的在同一个区域（归纳，前面的位置已经满足了第4条性质，如果前面没有了那就只能连向$j$了），那不如和左边那段区域缩在一起。

然后我们可以用$f_{i,j,k}$来表示状态：做到第$i$个点，$j$和$k$分别如上面所示。

转移：

$f_{i,j,k}\to f_{i+1,j,k}+posi(i+1,j)+nega(i+1,k)$，表示和前面的合成一块。

$f_{i,j,k}\to f_{i+1,k+1,i}+posi(i+1,k+1)+nega(i+1,i)$，表示新开一块。

时间复杂度$O(n^3)$。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 510
#define ll long long
int n;
int a[N][N];
ll p[N][N],q[N][N];
ll f[2][N][N];
void upd(ll &a,ll b){
    a=max(a,b);}
int main(){
    scanf("%d",&n);ll sum=0;for (int i=1;i<=n;++i){
    for (int j=1;j<i;++j)scanf("%d",&a[i][j]),sum+=a[i][j];for (int j=i+1;j<=n;++j)scanf("%d",&a[i][j]),sum+=a[i][j];}for (int i=1;i<=n;++i){
    for (int j=i-1;j>=1;--j)p[i][j]=p[i][j+1]+a[i][j];for (int j=1;j<i;++j)q[i][j]=q[i][j-1]+a[j][i];}int now=1,las=0;memset(f[now],128,sizeof f[now]);f[now][1][0]=0;for (int i=1;i<n;++i){
    swap(now,las);memset(f[now],128,sizeof f[now]);for (int j=1;j<=i;++j)for (int k=j-1;k<i;++k)if (f[las][j][k]>=0){
    upd(f[now][j][k],f[las][j][k]+p[i+1][j]+q[i+1][k]);upd(f[now][k+1][i],f[las][j][k]+p[i+1][k+1]+q[i+1][i]);}}ll ans=0;for (int j=1;j<=n;++j)for (int k=j-1;k<n;++k)upd(ans,f[now][j][k]);printf("%lld\n",sum-ans);return 0;
}