文档章节

4609: [Wf2016]Branch Assignment 最短路 DP (阅读理解题)

o
 osc_z1hvg4cu
发布于 2018/04/24 22:02
字数 1222
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Bzoj的翻译出锅了所以来官方题面:

这个题应该是单向边而BZOJ说的是双向边,什么你WA了?谁叫你懒得看英文......

显然我们能正向反向两遍SPFA处理出每个点到总部的距离和总部到每个点的距离。
如果某个点所在的部门的大小为S,那么这个点需要送出S-1次消息并接收S-1次消息。
我们把每个点的两个距离求和并排序,显然在一个块中的是这个序列上的一个区间(脑补一下为什么不这样不优),我们做一下前缀和。
然后就开始DP了,f[i][j]表示前i个点分j个块,最小代价。f[i][j] = min( f[k][j-1] + ( i - k - 1 ) * ( sum[i] - sum[k] ) )。
这个DP是O(n^3)的,考虑优化。
显然更小的边权所在的块应该更大,所以我们能从区间[i-(i/j),i-1]枚举k,这样能优化到n^2logn。
然而有更优美的做法:显然随着j增大,对于每个i最优的k也是递增的,直接指针扫过去,复杂度O(n^2)。
两种做法都可以AC,反正我6代i5的机器上时间差异不大,不知道BZOJ能不能卡出来(我只交了第一种)。
(为什么我现在在刷这种水题?我也不知道啊!!!)

第一种代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 typedef long long int lli;
 7 using namespace std;
 8 const int maxn=5e3+1e2,maxe=5e4+1e2;
 9 
10 lli su[maxn],f[2][maxn];
11 int b,s,cur;
12 
13 struct Graph {
14     int s[maxn],t[maxe],nxt[maxe],l[maxe],dis[maxn],inq[maxn],cnt;
15     inline void addedge(int from,int to,int len) {
16         t[++cnt] = to , l[cnt] = len , nxt[cnt] = s[from] , s[from] = cnt;
17     }
18     inline void spfa(int st) {
19         memset(dis,0x3f,sizeof(dis)) , dis[st] = 0;
20         queue<int> q; q.push(st) , inq[st] = 1;
21         while( q.size() ) {
22             const int pos = q.front(); q.pop() , inq[pos] = 0;
23             for(int at=s[pos];at;at=nxt[at])
24                 if( dis[t[at]] > dis[pos] + l[at] ) {
25                     dis[t[at]] = dis[pos] + l[at];
26                     if( !inq[t[at]] ) q.push(t[at]);
27                 }
28         }
29     }
30 }gra,rev;
31 
32 inline void dp() {
33     for(int i=1;i<=b;i++) su[i] = (lli) gra.dis[i] + rev.dis[i];
34     sort(su+1,su+1+b) , memset(f,0x3f,sizeof(f)) , **f = 0;
35     for(int i=1;i<=b;i++) su[i] += su[i-1];
36     for(int j=1;j<=s;j++) { // j is number of groups .
37         cur ^= 1 , memset(f[cur],0x3f,sizeof(f[1]));
38         for(int i=1;i<=b;i++) // i is last node .
39             for(int lst=i/j;lst;lst--)
40                 f[cur][i] = min( f[cur][i] , f[cur^1][i-lst] + ( lst - 1 ) * ( su[i] - su[i-lst] ) );
41     }
42 }
43 
44 int main() {
45     static int n,r;
46     scanf("%d%d%d%d",&n,&b,&s,&r);
47     for(int i=1,a,b,l;i<=r;i++) scanf("%d%d%d",&a,&b,&l) , gra.addedge(a,b,l) , rev.addedge(b,a,l);
48     gra.spfa(b+1) , rev.spfa(b+1) , dp();
49     printf("%lld\n",f[cur][b]);
50     return 0;
51 }
View Code

第二种代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 typedef long long int lli;
 7 using namespace std;
 8 const int maxn=5e3+1e2,maxe=5e4+1e2;
 9 
10 int tp[maxn];
11 lli su[maxn],f[2][maxn];
12 int b,s,cur;
13 
14 struct Graph {
15     int s[maxn],t[maxe],nxt[maxe],l[maxe],dis[maxn],inq[maxn],cnt;
16     inline void addedge(int from,int to,int len) {
17         t[++cnt] = to , l[cnt] = len , nxt[cnt] = s[from] , s[from] = cnt;
18     }
19     inline void spfa(int st) {
20         memset(dis,0x3f,sizeof(dis)) , dis[st] = 0;
21         queue<int> q; q.push(st) , inq[st] = 1;
22         while( q.size() ) {
23             const int pos = q.front(); q.pop() , inq[pos] = 0;
24             for(int at=s[pos];at;at=nxt[at])
25                 if( dis[t[at]] > dis[pos] + l[at] ) {
26                     dis[t[at]] = dis[pos] + l[at];
27                     if( !inq[t[at]] ) q.push(t[at]);
28                 }
29         }
30     }
31 }gra,rev;
32 
33 inline void dp() {
34     for(int i=1;i<=b;i++) su[i] = (lli) gra.dis[i] + rev.dis[i];
35     sort(su+1,su+1+b) , memset(f,0x3f,sizeof(f)) , **f = 0;
36     for(int i=1;i<=b;i++) su[i] += su[i-1];
37     for(int j=1;j<=s;j++) { // j is number of groups .
38         cur ^= 1 , memset(f[cur],0x3f,sizeof(f[1]));
39         for(int i=1;i<=b;i++) // i is last node .
40             for(int lst=tp[i];lst<i;lst++)
41                 if( f[cur][i] >= f[cur^1][lst] + ( i - lst - 1 ) * ( su[i] - su[lst] ) ) f[cur][i] = f[cur^1][lst] + ( i - lst - 1 ) * ( su[i] - su[lst] ) , tp[i] = lst;
42     }
43 }
44 
45 int main() {
46     static int n,r;
47     scanf("%d%d%d%d",&n,&b,&s,&r);
48     for(int i=1,a,b,l;i<=r;i++) scanf("%d%d%d",&a,&b,&l) , gra.addedge(a,b,l) , rev.addedge(b,a,l);
49     gra.spfa(b+1) , rev.spfa(b+1) , dp();
50     printf("%lld\n",f[cur][b]);
51     return 0;
52 }
View Code


良心的我给的数据下载:
链接:https://pan.baidu.com/s/19EmgxmCYDASzpTaqr0alkA 密码:00qr

果てないこの闇の向こうにも
在无尽的这黑暗的对面
光があると信じてる
我相信也存在光明
ここから生まれ変わる世界だけ
从此只盯住这脱胎换骨的世界
见つめて离さないよ
目不转睛
広がるこの空を见上げると
仰望这广袤的天空
あの日の戦いが映る
那一日的决战映在脑海
いつかは全て消えてしまうのか
终有一天一切将会消失
栄光を取り戻せ
重新夺回这荣光

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
BZOJ_4609_[Wf2016]Branch Assignment_决策单调性+带权二分

BZOJ4609[Wf2016]Branch Assignment_决策单调性+带权二分 Description 要完成一个由s个子项目组成的项目,给b(b>=s)个部门分配,从而把b个部门分成s个组。分组完成后,每一组的任 意两个点之...

osc_t6kfzq66
2018/06/24
2
0
带权二分

带权二分 一种二分答案的套路,又叫做DP凸优化,wqs二分。 用来解决一类题目,要求某个要求出现K次,并且,可以很显然的发现,在改变相应权值的时候,对应出现的次数具有单调性。而且很显然,...

osc_o60il3e6
2018/11/28
2
0
bzoj4609: [Wf2016]Branch Assignment

Description 要完成一个由s个子项目组成的项目,给b(b>=s)个部门分配,从而把b个部门分成s个组。分组完成后,每一组的任意两个点之间都要传递信息。假设在(i,j)两个点间传送信息,要先把信息...

cdsszjj
2018/05/15
0
0
WF2016 BranchAssignment

Link Difficulty 算法难度5,思维难度6,代码难度5 Description 给定一张n个点r条边的有向图,边有长度,其中编号1~b是部门,b+1号是总部。 现在要求你将所有部门分成s组,每组的所有部门之间...

stone41123
04/01
0
0
CCPC 2016-2017, Finals Solution

A - The Third Cup is Free 水。 1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1e5 + 10; 6 7 int n; 8 int arr[maxn]; 910 int main()11 {12 int t;13 scanf(......

osc_gz5w458v
2018/11/10
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
51分钟前
16
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
今天
24
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
今天
7
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
今天
25
0
63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
今天
55
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部