题目
思路
题目意思很简单。网络流建模很容易。
每个点开两个点 i i i 和 i ′ i' i′ ，前者用来完成通信，后者是用于被别人接入。 S → i → j ′ → T S\rightarrow i\rightarrow j'\rightarrow T S→i→j′→T 表示 i i i 接在 j j j 后面，所以 S → i S\rightarrow i S→i 的容量为 1 1 1 、代价为 0 0 0 、要求满流； i → j ′ i\rightarrow j' i→j′ 容量无所谓、代价为 ∣ a i − a j ∣ |a_i-a_j| ∣ai−aj∣ 、没特殊要求； j ′ → T j'\rightarrow T j′→T 容量为 1 1 1（最多被后面的一个哨站连接）、代价为 0 0 0 、没特殊要求。
还有一种选择，连接控制中心。所以 i → T i\rightarrow T i→T 容量无所谓、代价为 W W W 即可。
此时有
O
(
n
2
)
\mathcal O(n^2)
O(n2) 条边。这是单位图，肯定可以随便跑。
考虑优化。把 j ′ j' j′ 分成两种， a j < a i a_j<a_i aj<ai 和 a j ≥ a i a_j\ge a_i aj≥ai 。前者为 j 1 ′ j_1' j1′ ，此时 i → j 1 ′ i\rightarrow j_1' i→j1′ 的代价是已知的 a i − a j a_i-a_j ai−aj ，改成 j 1 ′ → T j_1'\rightarrow T j1′→T 代价为 − a j -a_j −aj 、 S → i S\rightarrow i S→i 代价为 a i a_i ai 也是等效的。类似的操作， S → i S\rightarrow i S→i 代价为 − a i -a_i −ai 而 j 2 ′ → T j_2'\rightarrow T j2′→T 代价为 a j a_j aj 也是可以的。
你发现 S → i S\rightarrow i S→i 的代价不统一。没关系，改成 S → i S\rightarrow i S→i 加上 i → i 1 i\rightarrow i_1 i→i1 和 i → i 2 i\rightarrow i_2 i→i2 就行。
所以现在问题变成了，找到所有 j < i , a j < a i j<i,\;a_j<a_i j<i,aj<ai 的 j j j 并连边 i 1 → j 1 ′ i_1\rightarrow j'_1 i1→j1′ ；找到所有 j < i , a j ≥ a i j<i,\;a_j\ge a_i j<i,aj≥ai 并连边 i 2 → j 2 ′ i_2\rightarrow j'_2 i2→j2′ 。这好像可以 可持久化线段树 做啊。
代码
这份代码有玄机。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
const int MaxM = 100005;
struct Edge{
int to, nxt, c, w;
Edge(){}
Edge(int T,int N,int C,int W){
to = T, nxt = N, c = C, w = W;
}
};
Edge e[MaxM<<1];
int head[MaxM], cntEdge;
void addEdge(int a,int b,int c,int d){
// if(a != 0 && b != 1)
// printf("%d -- %d --> %d\n",a,d,b);
e[cntEdge] = Edge(b,head[a],c,d);
head[a] = cntEdge ++;
e[cntEdge] = Edge(a,head[b],0,-d);
head[b] = cntEdge ++;
}
const int_ infty = (1ll<<60)-1;
const int bigint = (1<<30)-1;
queue< int > q; int_ dis[MaxM];
bool inQue[MaxM]; int pre[MaxM];
bool spfa(int x,int t,int n){
fill(dis,dis+n,infty);
q.push(x); dis[x] = pre[x] = 0;
while(!q.empty()){
x = q.front(); q.pop();
inQue[x] = false;
// printf("x = %d with dis = %lld\n",x,dis[x]);
for(int i=head[x]; ~i; i=e[i].nxt)
if(e[i].c && dis[e[i].to] > dis[x]+e[i].w){
dis[e[i].to] = dis[x]+e[i].w;
pre[e[i].to] = i; // id of edge
if(!inQue[e[i].to]){
q.push(e[i].to);
inQue[e[i].to] = true;
}
}
}
return dis[t] != infty;
}
int_ ek(int s,int t,int n){
int_ res = 0; int sy;
while(spfa(s,t,n)){
// puts("FUCK");
sy = e[pre[t]].c; // capacity
for(int x=t; x!=s; x=e[pre[x]^1].to)
sy = min(sy,e[pre[x]].c);
for(int x=t; x!=s; x=e[pre[x]^1].to){
e[pre[x]].c -= sy;
e[pre[x]^1].c += sy;
}
// printf("add %d*%lld\n",sy,dis[t]);
res += sy*dis[t];
}
return res;
}
int son[MaxM][2], id[MaxM];
int totNode, nowId; // allocate id
/** @brief hang up @p leaf on the @p qid location */
void modify(int qid,int leaf,int rt,int &o,int l,int r){
o = ++ totNode; id[o] = ++ nowId;
if(rt) addEdge(id[o],id[rt],bigint,0);
son[o][0] = son[rt][0];
son[o][1] = son[rt][1];
if(l == r){
addEdge(id[o],leaf,bigint,0);
return ;
}
if(qid <= ((l+r)>>1)){
modify(qid,leaf,son[rt][0],
son[o][0],l,(l+r)>>1);
addEdge(id[o],id[son[o][0]],bigint,0);
}
else{
modify(qid,leaf,son[rt][1],
son[o][1],(l+r)/2+1,r);
addEdge(id[o],id[son[o][1]],bigint,0);
}
}
void query(int ql,int qr,int leaf,int o,int l,int r){
if(!o) return ; // nothing here
if(ql <= l && r <= qr)
return addEdge(leaf,id[o],bigint,0);
if(ql <= ((l+r)>>1))
query(ql,qr,leaf,son[o][0],l,(l+r)>>1);
if(((l+r)>>1) < qr)
query(ql,qr,leaf,son[o][1],(l+r)/2+1,r);
}
const int MaxN = 1005;
int allA[MaxN], a[MaxN];
//int fuck[MaxN][3];
int main(){
int n = readint(), W = readint();
memset(head,-1,MaxM<<2); // don't forget
for(int i=1; i<=n; ++i)
allA[i] = a[i] = readint();
sort(allA+1,allA+n+1);
int *endA = unique(allA+1,allA+n+1);
nowId = 1; // S = 0, T = 1
for(int i=1,rt1=0,rt2=0; i<=n; ++i){
int rnk = lower_bound(allA+1,endA,a[i])-allA;
int x = ++ nowId; // i
addEdge(0,x,1,0); // must full
addEdge(x,1,1,W); // direct link
int x1 = ++ nowId; // a_i - a_j
addEdge(x,x1,1,a[i]);
query(1,rnk,x1,rt1,1,endA-allA-1);
// for(int j=1; j<i; ++j)
// if(a[j] <= a[i])
// addEdge(x1,fuck[j][1],bigint,0);
int x2 = ++ nowId; // a_j - a_i
addEdge(x,x2,1,-a[i]);
// for(int j=1; j<i; ++j)
// if(a[j] > a[i])
// addEdge(x2,fuck[j][2],bigint,0);
if(rnk != endA-allA-1)
query(rnk+1,bigint,x2,rt2,1,endA-allA-1);
x = ++ nowId; // i'
addEdge(x,1,1,0); // at most one
x1 = ++ nowId; // a_? - a_i
// fuck[i][1] = x1;
addEdge(x1,x,1,-a[i]);
modify(rnk,x1,rt1,rt1,1,endA-allA-1);
x2 = ++ nowId; // a_i - a_?
// fuck[i][2] = x2;
addEdge(x2,x,1,a[i]);
modify(rnk,x2,rt2,rt2,1,endA-allA-1);
}
printf("%lld\n",ek(0,1,nowId+1));
return 0;
}
玄机就是它只能过 80 p t s 80pts 80pts ，剩下的 T L E TLE TLE 了。