决策单调性

四边形不等式

对于 \(\mathtt{dp}\) 转移的花费（\(a\le b\le c\le d\)），首先要满足这样的柿子：

\[w(a,c)+w(b,d)\le w(a,d)+w(b,c) \]

注意，符号也可以取 "\(\ge\)"，这个视题目要求而定。另外注意 \(w(x,y)\) 的定义是 "从 \(x\) 转移到 \(y\) 的花费"。

决策单调

以 \(\mathtt{dp}\) 转移到

\[dp_i=\min\{dp_j+w(j,i)\} \]

为例。假设 \(w\) 满足条件 "\(\le\)"。

令点 \(i\) 的决策点为 \(p_i\)，首先需要 默认 \(p_i \le i\)。

那么有：

\[dp_{p_i}+w(p_i,i)\le dp_j+w(j,i)\\ dp_{p_{i+1}}+w(p_{i+1},i+1)\le dp_j+w(j,i+1) \]

若 \(p_{i+1}\ge i\)，那么有 \(p_{i+1}\ge p_i\)，得证。

反之，可以把柿子替换成

\[dp_{p_i}+w(p_i,i)\le dp_{p_{i+1}}+w(p_{i+1},i)\\ dp_{p_{i+1}}+w(p_{i+1},i+1)\le dp_{p_i}+w(p_i,i+1) \]

将两式相加，得到：

\[w(p_i,i)+w(p_{i+1},i+1)\le w(p_{i+1},i)+w(p_i,i+1) \]

套用四边形不等式，就可以得到 \(p_i\le p_{i+1}\)，得证。

另外再提一嘴，转移方程中并不需要保证前后是同一个数组。

套路

\(p_i\le p_{i+1}\)："\(\le\)" 且 \(\min\)；"\(\ge\)" 且 \(\max\)。
\(p_i\ge p_{i+1}\)："\(\ge\)" 且 \(\min\)；"\(\le\)" 且 \(\max\)。

\(\text{wqs}\) 二分

[国家集训队]\(\text{ Tree I}\)

解法

令 \(g(m)\) 为选 \(m\) 条白边得到最小生成树的权值。这个函数是下凸的，具体可以这样感性证明 —— 设选 \(k\) 条白边时正好得到无限制的最小生成树，那么往右/左选都只可能用不优的白边替换黑边；或用不优的黑边替换白边。

考虑 \(\text{wqs}\) 二分。二分斜率为 \(\rm mid\) 的直线切那个凸包，显然切点就是截距最小的点，令 \(f(m)=g(m)-m\cdot \rm mid\)，将所有白边减去 \(\rm mid\)，求出最小生成树，其对应的权值即为 \(f(m)\)，记录选出的白边 \(m'\)。由于斜率增大时，选择白边数增大，可以依据此调整斜率。

但是会不会出现这样的情况：二分 \(\text{mid},\text{mid}+1\) 时，得到的白边数分别为 \(x,x+\delta(\delta >1)\)，这样就会忽略掉 \(x+\Delta=\text{need}(1\le \Delta <\delta)\) 的情况。

事实上，只要当白边黑边权值相等时选择白边就可以保证求出最小生成树答案正确。假设面对上文的情况，最终得到的二分值为 \(\rm mid\)。考虑增加 \(\delta\) 条白边满足什么条件：在 \(\text{mid}\) 状态下，有 \(\delta\) 条白边的权值为 \(\delta\) 条不同黑边的权值 \(+1\)。此时一定可以将白边用黑边替换，从而得到 \(\rm need\) 条白边。这种 "替换" 这也是输出方案是 \(\rm wqs\) 二分的瓶颈的原因。

实现可以使用双指针，复杂度 \(\mathcal O(m\log(m+V))\)。

代码

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=5e4+5,maxm=1e5+5;

int n,m,Need,cnt,tot,sum,f[maxn],MinSum;
struct Edge {
	int u,v,w;
	
	bool operator < (const Edge t) const {
		return w<t.w;
	}
} e[maxm];

bool init() {rep(i,1,n) f[i]=i;}

int Find(int x) {return x==f[x]?x:f[x]=Find(f[x]);}

void addEdge(int i,int w) {
	int x=Find(e[i].u),y=Find(e[i].v);
	if(x^y) {
		sum+=w,f[x]=y;
		if(i<=cnt) ++tot;
	}
}

int main() {
	n=read(9),m=read(9),Need=read(9);
	rep(i,1,m) {
		e[i].u=read(9)+1,e[i].v=read(9)+1,e[i].w=read(9);
		if(!read(9)) swap(e[++cnt],e[i]);
	}
	sort(e+1,e+cnt+1),sort(e+cnt+1,e+m+1); 
	int l=-100,r=100,mid,p,q;
	while(l<r) {
		mid=l+r+1>>1;
		init(),sum=tot=p=0,q=cnt;
		while(p<cnt && q<m)
			if(e[p+1].w+mid<=e[q+1].w) ++p,addEdge(p,e[p].w+mid);
			else ++q,addEdge(q,e[q].w);
		while(p<cnt) ++p,addEdge(p,e[p].w+mid);
		while(q<m) ++q,addEdge(q,e[q].w);
		if(tot<Need) r=mid-1;
		else MinSum=sum,l=mid;
	}
	print(MinSum-l*Need,'\n');
	return 0;
}

[八省联考 2018] 林克卡特树

题目描述

割掉 \(k\) 条边之后会出现 \(k+1\) 个联通块，那么对于每一个联通块求直径再用 \(k\) 条边将这 \(k+1\) 个联通块串起来即可，所以问题转化为：给定一棵 \(n\) 个点的树，边权有正有负，要求在树上选出 \(k+1\) 条链，使得其权值之和最大。

注意，单个节点也是一条链，它的权值为零。

解法

首先进行一个朴素 \(\mathtt{dp}\)。

令 \(g(m)=dp_{1,m,0}\)，则 \((m,g(m))\) 形成一个上凸包。为啥捏？考虑上凸满足条件为 \(g(i)-g(i-1)\ge g(i+1)-g(i)\)，考虑每增加一条链一定优先选择更优的。当链的个数足够多时，有些链被划分成点，就会丢失边权；或者增加负边权链。而且我们发现 \(g(0)=g(n)=0\)（全是点就无边权了），一定程度上证实了这个猜想。

\(\rm wqs\) 二分过程就略过了，和上面是一样的~ 需要注意 \(\mathtt{dp}\) 过程中还需要求出最小权值对应的链数。

如果凸包上有点共线咋办？这个没有关系，可以钦定选最左/右的点，我们需要的只是斜率。

另外就是 \(\rm mid\) 为什么是整数的问题。考虑问题就是在 \(g\) 的凸包上找切点 \((m,g(m))\) 的问题，由于 \(g\) 为整数，所以经过 \((m,g(m)),(m+1,g(m+1))\) 的直线斜率一定是整数。

代码

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

#include <iostream>
using namespace std;
typedef long long ll;

const int maxn=3e5+5;

int n,k;
int cnt,head[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1];
struct node {
	ll val; int num;
	
	friend bool operator < (const node x,const node y) {
		return (x.val^y.val)?x.val<y.val:x.num>y.num;
	}
	
	friend node operator + (const node x,const node t) {
		return (node){x.val+t.val,x.num+t.num};
	}
	
	friend node operator + (const node x,const int t) {
		return (node){x.val+t,x.num};
	}
} f[maxn][3],e;

void addEdge(int u,int v,int w) {
	nxt[++cnt]=head[u],to[cnt]=v,val[cnt]=w,head[u]=cnt;
	nxt[++cnt]=head[v],to[cnt]=u,val[cnt]=w,head[v]=cnt;
}

void dfs(int u,int fa) {
	f[u][0]=f[u][1]=f[u][2]=(node){0,0};
	erep(i,u) {
		if(v==fa) continue;
		dfs(v,u);
		f[u][2]=max(f[u][2],max(f[u][1]+f[v][1]+val[i]+e,f[u][2]+f[v][0]));
		f[u][1]=max(f[u][1],max(f[u][1]+f[v][0],f[u][0]+f[v][1]+val[i]));
		f[u][0]=max(f[u][0],f[u][0]+f[v][0]);
	}
	f[u][0]=max(f[u][0],max(f[u][2],f[u][1]+e));
}

int main() {
	n=read(9),k=read(9)+1;
	rep(i,1,n-1) {
		int u=read(9),v=read(9),w=read(9);
		addEdge(u,v,w);
	}
	ll l=-1e12,r=1e12,mid;
	while(l<r) {
		mid=(l+r)>>1;
		e=(node){-mid,1};
		dfs(1,0);
		if(f[1][0].num==k) return print(f[1][0].val+1ll*mid*k,'\n'),0;
		if(f[1][0].num>k) l=mid+1;
		else r=mid;
	}
	e=(node){-l,1};
	dfs(1,0);
	print(f[1][0].val+1ll*l*k,'\n');
	return 0;
}