bzoj4609(最短路+贪心+wqs二分+决策单调性)

|

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4609

https://codeforces.com/gym/101242/problem/B

题意

$bzoj$ 题面有误，推荐原题面

给定 $n$ 个点和 $r$ 条边的有向图。若将 $i$ 点信息传输到 $j$ 点，那么要从 $i$ 走向 $b+1$ 再走向 $j$ 。现把前 $b$ 个点分成 $s$ 个组，每一个组两两之间要传递一次信息，问距离总和的最小值。

题解

这个题意感觉比较沙雕。。显然只有这 $b$ 个点的事情，那么先对 $b+1$ 正反跑一遍最短路，然后发现每个点的贡献等于 (所在组的大小-1)*正反距离和

然后将 $b$个点分成 $s$ 个组实在是很头疼，然而如果每个组的大小固定，我们必定是将距离和大的放在比较小的组里面，所以可以发现分组的时候总是可以优先考虑距离和大的点，那么可以根据距离和排序之后，转化成对序列的分割

然后就可以 $DP$ 了，而且可以用 $wqs$ 二分优化

然后设 $dp[i]$ 为到 $i$ 的最小距离，$d[i]$ 为距离和的前缀和，有
$ dp[i]=max { dp[j]+(i-j-1)(d[i]-d[j])+t }$
发现后面的 $cost$ 是个凸函数，可以用决策单调性优化

复杂度为 $O(blogblogC)​$

卡进 $#1$ 真开心_(:3 」∠)_




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-6
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 5005
#define nm 100005
#define pi 3.1415926535897931
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}





struct edge{int t,v;edge*next;}e[nm],*h[NM],*o=e,*_h[NM];
void add(int x,int y,int v){o->t=y;o->v=v;o->next=h[x];h[x]=o++;}
void _add(int x,int y,int v){o->t=y;o->v=v;o->next=_h[x];_h[x]=o++;}
int n,m,_p,_x,_y,qh,qt,q[NM],_t,v[NM],_n,_d[NM],__d[NM];
ll d[NM],dp[NM],ans;
int p[NM];
struct tmp{
    int x;ll d;
    bool operator<(const tmp&o)const{return d>o.d;}
};

void dij(){
    priority_queue<tmp>q;
    inc(i,1,n)__d[i]=1e9;
    q.push(tmp{_n+1,__d[_n+1]=0});
    while(!q.empty()){
	int t=q.top().x,cnt=q.top().d;q.pop();
	if(cnt!=__d[t])continue;
	link(t)if(__d[j->t]>__d[t]+j->v)q.push(tmp{j->t,__d[j->t]=__d[t]+j->v});
    }
}
#define _link(x) for(edge *j=_h[x];j;j=j->next)
void _dij(){
    priority_queue<tmp>q;
    inc(i,1,n)_d[i]=1e9;
    q.push(tmp{_n+1,_d[_n+1]=0});
    while(!q.empty()){
	int t=q.top().x,cnt=q.top().d;q.pop();
	if(cnt!=_d[t])continue;
	_link(t)if(_d[j->t]>_d[t]+j->v)q.push(tmp{j->t,_d[j->t]=_d[t]+j->v});
    }
}

bool check(ll t){
    q[qh=qt=1]=0;v[0]=0;
    inc(i,1,n){
	while(qh<qt&&v[q[qh+1]]<=i)qh++;
	v[q[qh]]=max(v[q[qh]],i+1);
	dp[i]=dp[q[qh]]+(i-q[qh]-1)*(d[i]-d[q[qh]])+t;
	p[i]=p[q[qh]]+1;
	while(qh<=qt&&dp[q[qt]]+(v[q[qt]]-q[qt]-1)*(d[v[q[qt]]]-d[q[qt]])>=dp[i]+(v[q[qt]]-i-1)*(d[v[q[qt]]]-d[i]))qt--;
	int s=i;
	if(qh<=qt){
	    s=n+1;
	    for(int x=v[q[qt]]+1,y=n;x<=y;){
		int mid=x+y>>1;
		if(dp[q[qt]]+(mid-q[qt]-1)*(d[mid]-d[q[qt]])>=dp[i]+(mid-i-1)*(d[mid]-d[i]))
		    s=mid,y=mid-1;else x=mid+1;
	    }
	}
	if(s<=n)v[i]=s,q[++qt]=i;
    }
    //printf("%lld %lld %d\n",t,dp[n],p[n]);
    return p[n]<m;
}

int main(){
    n=read();_n=read();m=read();_p=read();
    while(_p--){_x=read();_y=read();_t=read();add(_x,_y,_t);_add(_y,_x,_t);}
    dij();_dij();
    //inc(i,1,n)printf("%d ",_d[i]);putchar('\n');
    n=_n;
    inc(i,1,n)d[i]+=__d[i]+_d[i];
    sort(d+1,d+1+n);reverse(d+1,d+1+n);
    inc(i,1,n)d[i]+=d[i-1];
    for(ll x=0,y=d[n]*n;x<=y;){
	ll mid=x+y>>1;
	if(check(mid))y=mid-1;else ans=dp[n]-mid*m,x=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}