SNOI2019 通信

【题解】[SNOI2019]通信

评价：一眼秒了，两个板子合在一起就成难题了是嘛 /怄火

题目描述：

$n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。

每个哨站 $i$ 需要选择以下二者之一：

1. 直接连接到控制中心，代价为 $W$；
2. 连接到前面的某个哨站 $j$ ($j<i$)，代价为 $|a_i-a_j|$。
   每个哨站只能被后面的至多一个哨站连接。

请你求出最小可能的代价和。

对于所有数据，$1 \leq n \leq 1000$，$0 \leq W,a_i \leq 10^9$。

题目分析：

一个想法就是 $dp$，但是这样的话我们就要记录每个点选/不选，这种东西就很不能做。
注意到一个哨站最多连接到前面的一个和后面的一个哨站。
这个东西就有一种匹配的感觉，而这个东西显然不是二分图，所以只有网络流这一种思路了。
所以就有一个显然的建图：
设源点为 $s$，汇点为 $t$，控制中心为 $p$，将哨站 $i$ 拆成一个入点 $in_i$ 和一个出点 $out_i$。
对于每一个哨站建边：$(s,in_i,1,0)$，$(out_i,t,1,0)$，$(in_i,p,1,W)$，$(in_i,out_j,1,\left| a_i-a_j \right|)$。
主要是最后这一种建边数量 $O(n^2)$，所以直接费用流的复杂度是接受不了的。
可以发现最后一种建边就相当于一个二维偏序，因为我们可以将绝对值拆开，即：

• 若 $j < i$ 且 $a_j < a_i$，建边 $(in_i,out_j,1,a_i-a_j)$。
• 若 $j < i$ 且 $a_j > a_i$，建边 $(in_i,out_j,1,a_j-a_i)$。

可以使用分治去掉第一维，这样第二维就可以使用前缀和优化建图解决了。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3005;
const int INF = 1e18+5;
struct edge{
	int nxt,to,cost,val;
	edge(){}
	edge(int _nxt,int _to,int _val,int _cost){
		nxt = _nxt,to = _to,cost = _cost,val = _val;
	}
}e[5000 * N];
int cnt=1,tot,s,t,pre[N],suf[N],b[N],tmp[N],in[5 * N],out[5 * N],a[5 * N],dis[5 * N],cur[5 * N],head[5 * N];
bool in_que[5 * N],vis[5 * N];
void add_edge(int from,int to,int val,int cost){
	e[++cnt] = edge(head[from],to,val,cost);
	head[from] = cnt;
	e[++cnt] = edge(head[to],from,0,-cost);
	head[to] = cnt;
}
bool spfa(){
	for(int i=1; i<=tot; i++)	dis[i] = INF,in_que[i] = false,cur[i] = head[i];
	dis[s] = 0;
	queue<int> q;q.push(s);in_que[s] = true;
	while(!q.empty()){
		int now = q.front();q.pop();
		in_que[now] = false;
		for(int i=head[now]; i; i=e[i].nxt){
			int to = e[i].to;
			if(dis[to] > dis[now] + e[i].cost && e[i].val){
				dis[to] = dis[now] + e[i].cost;
				if(!in_que[to])	q.push(to),in_que[to] = true;
			}
		}
	}
	return dis[t] != INF;
}
int dfs(int now,int limit){
	if(now == t)	return limit;
	int flow = 0;vis[now] = true;
	for(int i=cur[now]; i && flow < limit; i=e[i].nxt){
		int to = e[i].to;
		cur[now] = i;
		if(e[i].val && dis[to] == dis[now] + e[i].cost && !vis[to]){
			int h = dfs(to,min(e[i].val,limit-flow));
			e[i].val -= h,e[i^1].val += h;
			flow += h;
			if(!h)	dis[to] = INF;
		}
	}
	return flow;
}
int dinic(){
	int ans = 0;
	while(spfa()){
		memset(vis,false,sizeof(vis));
		int flow = dfs(s,INF);
		ans += flow * dis[t];
	}
	return ans;
}
int find(int l,int r,int val){
	int ans = r + 1;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(a[b[mid]] > val){
			ans = mid,r = mid - 1;
		}
		else	l = mid + 1;
	}
	return ans;
}
void solve(int l,int r){
	if(l == r)	return;
	int mid = (l + r) >> 1;
	solve(l,mid);solve(mid+1,r);
	for(int i=l; i<=mid; i++){
		pre[i] = ++tot;
		add_edge(pre[i],out[b[i]],1,-a[b[i]]);
		if(i != l)	add_edge(pre[i],pre[i-1],INF,0);
	}
	for(int i=mid; i>=l; i--){
		suf[i] = ++tot;
		add_edge(suf[i],out[b[i]],1,a[b[i]]);
		if(i != mid)	add_edge(suf[i],suf[i+1],INF,0);
	}
	
	for(int i=mid+1; i<=r; i++){
		int pos = find(l,mid,a[b[i]]);  //第一个大于 a[b[i]] 的数
		if(pos-1 >= l)	add_edge(in[b[i]],pre[pos-1],1,a[b[i]]);
		if(pos <= mid)	add_edge(in[b[i]],suf[pos],1,-a[b[i]]); 
	}
	int sz = l-1;
	int posl = l,posr = mid+1;
	while(posl <= mid && posr <= r){
		if(a[b[posl]] < a[b[posr]])	tmp[++sz] = b[posl++];
		else	tmp[++sz] = b[posr++];
	}
	while(posl <= mid)	tmp[++sz] = b[posl++];
	while(posr <= r)	tmp[++sz] = b[posr++];
	for(int i=l; i<=r; i++)	b[i] = tmp[i];
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,W;scanf("%lld%lld",&n,&W);
	s = ++tot;
	t = ++tot;
	int p = ++tot;add_edge(p,t,INF,0);
	for(int i=1; i<=n; i++)	in[i] = ++tot,out[i] = ++tot;
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		add_edge(s,in[i],1,0);add_edge(out[i],t,1,0);
		add_edge(in[i],p,1,W);
	}
	
	for(int i=1; i<=n; i++)	b[i] = i;
	solve(1,n);
	
	printf("%lld\n",dinic());
	return 0;
}