[bzoj4919] [Wf2016]Branch Assignment

思路

先正反两遍最短路预处理每个点$i$到总部的距离和总部到$i$的距离之和 v a l i val_{i} vali​。
如果$i$所在组大小为$k$，则贡献为$i\ast (k-1)$。
显然，调整法可以证明，最优解肯定是权值大小相邻的在同一组，所以排序后求出 v a l i val_{i} vali​的前缀和 s u m i sum_{i} sumi​就可以dp了。
可以写出转移方程：
$dp[i][k]=min(dp[j][k-1]+(sum[i]-sum[j])\ast (i-j-1))(j<i)$。
直接转移是 O ( n 3 ) O(n^{3}) O(n3)的，然而我们可以发现，因为 v a l i val_{i} vali​是从小到大排序的，所以每段的长度是单调不增的，所以$j$的取值是在$[i-i/k,i)$之间，这是个调和级数求和，这样复杂度就优化到了 O ( n 2 l o g n ) O(n^{2}log_{n}) O(n2logn​)了。

代码

#include
#include
#include
#include
#include
#define ll long long
#define maxn 5050
#define maxm 50050
using namespace std;
int n,b,s,m,tu[maxm],tv[maxm],tl[maxm];
void init(){scanf("%d%d%d%d",&n,&b,&s,&m);for(int i=1;i<=m;++i)scanf("%d%d%d",&tu[i],&tv[i],&tl[i]);
}
int tot,la[maxn];
struct edge{int v,ne,l;}e[maxm];
inline void add(int u,int v,int l){e[tot].v=v,e[tot].ne=la[u],e[tot].l=l,la[u]=tot++;
}
ll d[maxn],val[maxn];
struct node{ll d;int id;};
inline bool operator<(const node &a,const node &b){return a.d>b.d;}
priority_queue<node>qu;
void dij(int s){while(!qu.empty())qu.pop();memset(d,127/2,sizeof(d));d[s]=0;qu.push((node){0,s});while(!qu.empty()){int u=qu.top().id;ll du=qu.top().d;qu.pop();if(du>d[u])continue;for(int i=la[u];~i;i=e[i].ne){int v=e[i].v,l=e[i].l;if(du+l<d[v]){d[v]=du+l;qu.push((node){d[v],v});}}}
}
void getval(){memset(val,0,sizeof(val));tot=0;memset(la,-1,sizeof(la));for(int i=1;i<=m;++i)add(tu[i],tv[i],tl[i]);dij(b+1);for(int i=1;i<=b;++i)val[i]+=d[i];tot=0;memset(la,-1,sizeof(la));for(int i=1;i<=m;++i)add(tv[i],tu[i],tl[i]);dij(b+1);for(int i=1;i<=b;++i)val[i]+=d[i];sort(val+1,val+b+1);
}
ll dp[2][maxn];
void solve(){getval();for(int i=2;i<=b;++i)val[i]+=val[i-1];memset(dp[0],127/2,sizeof(dp[0]));dp[0][0]=0;for(int k=1;k<=s;++k){int now=k&1,lst=now^1;memset(dp[now],127/2,sizeof(dp[now]));for(int i=1;i<=b;++i)for(int j=i-i/k;j<i;++j)dp[now][i]=min(dp[now][i],dp[lst][j]+(val[i]-val[j])*(i-j-1));}printf("%lld\n",dp[s&1][b]);
}
int main(){init(); solve();return 0;
}

update

当然神犇可以用凸优化+决策单调性 O （ n l o g n 2 ) O（nlogn^{2}) O（nlogn2)轻松切掉此题辣。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！