题解 CF724E 【Goods transportation】
panyf
2020-06-06 23:40:27
$O(n\log n)$ 的解法
首先，很显然的网络流做法就是从源点 $S$ 向 $i$ 连权值为 $p_i$ 的边，从 $i$ 向汇点 $T$ 连权值为 $s_i$ 的边，对于任意 $i<j$ 从 $i$ 向 $j$ 连权值为 $c$ 的边，求最大流即可。
本题最重要的一点就是将最大流转化为最小割，用 dp 求出。令 $f_{i,j}$ 表示 dp 到点 $i$ ，有 $j$ 个点到 $S$ 的边未割掉。若割掉 $i$ 到 $S$ 的边，则还需割掉 $i$ 到那 $j$ 个点的边，即 $f_{i,j}=f_{i-1,j}+p_i+c\times j$ 。若割掉 $i$ 到 $T$ 的边，则 $f_{i,j}=f_{i-1,j-1}+s_i$ 。注意 $i$ 这一维要滚掉，时间复杂度 $O(n^2)$ ，已经能够通过本题。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10003;
ll u[N],v[N],p[N];
int main(){
int i,j,n;
ll*f=u,*g=v,w=1e18,c,q;
cin>>n>>c;
for(i=1;i<=n;++i)cin>>p[i];
for(i=1;i<=n;++i){
swap(f,g),cin>>q,f[0]=g[0]+p[i],f[i]=g[i-1]+q;
for(j=1;j<i;++j)f[j]=min(g[j-1]+q,g[j]+p[i]+c*j);
}
cout<<*min_element(f,f+n+1);
return 0;
}
```
考虑贪心优化。令 $a_i=c\times(n-i)+s_i-p_i$ ，并将 $a$ 数组从小到大排序。开始先割掉所有到 $S$ 的边，之后按顺序依次割掉到 $T$ 的边并恢复到 $S$ 的边。当割掉 $a_i$ 代表的点到 $T$ 的边时，答案加上 $a_i-c_i\times(i-1)$ 。减去 $c_i\times(i-1)$ 是因为之前的 $i-1$ 个点到当前点的权值为 $c$ 的边已经被割掉了，就不用再加上了。
至此，贪心的正确性也很显然了。考虑任意 $i<j$ ，若 $a_i$ 代表的点割掉了到 $S$ 的边，而 $a_j$ 代表的点割掉了到 $T$ 的边，那么我们让 $a_i$ 割掉到 $T$ 的边， $a_j$ 割掉到 $S$ 的边，答案就会增加 $a_i-a_j$ ，而 $a_i-a_j<0$ ，所以答案更优。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int p[10003];
ll a[10003];
int main(){
int n,s,i;
ll w,c,o=0;
cin>>n>>c;
for(i=1;i<=n;++i)cin>>p[i],o+=p[i];
for(i=1;i<=n;++i)cin>>s,a[i]=c*(n-i)+s-p[i];
w=o,sort(a+1,a+n+1);
for(i=1;i<=n;++i)w=min(w,o+=a[i]-c*(i-1));
cout<<w;
return 0;
}
```