Rikka with K-Match
Yuta has a graph (G) with (n) nodes ((i,j)(1 leq i leq n,1 leq j leq m)). There is an edge between ((a,b)) and ((c,d)) if and only if (|a-c|+|b-d|=1). Each edge has its weight.
Now Yuta wants to calculate the minimum weight (K)-matching of (G).
(1 leq n leq 4 imes 10^4,1 leq m leq 4)
题解
https://blog.csdn.net/The_star_is_at/article/details/76919415
应该是一个经典的 Idea 了。令 (w_i) 为匹配数为 (i) 时的最小匹配，那么因为匹配是一个费用流问题，所以一定有 (w_{i+1}-w_{i} geq w_{i}-w_{i-1})。
考虑把 (w_i) 看成平面上的点 ((i,w_i))，那么显然所有点都分布在一个下凸壳上，因此肯定存在一个斜率 (d)，使得这个斜率的直线与下凸壳的切点恰好为 ((K,w_K))，即 ((K,w_K)) 为 (w_i-id) 最小的点，这相当于把边权减去 (d) 后的最小匹配。
因此可以二分斜率 (d)，然后求出边权全部减去 (d) 后的最小匹配的值以及最小匹配中有多少条边，根据最小匹配中的边数和 (K) 的大小关系来决定二分的方向。这样问题就转化成了求 (O(log n)) 次网格图最大匹配。这是一个轮廓线 DP 的经典问题，可以在 (O(nm2^m)) 内解决。
因此总的时间复杂度为 (O(nm2^mlog n))。
要注意的是二分上界不能设为 (10^9) 级别，考虑一条 (1) 和 (10^9) 交错的链，那么在最后一次增广的时候所有的 (1) 都会变成 (10^9)，因此二分上界应该是 (10^9 imes frac{nm}{2})，标程把上界设为了 (10^{14})，DP 时刚好不会爆 long long。
CO int64 inf=1e18;
int n,m,A[40001][4],B[40001][4];
int64 f[2][5][1<<4];int g[2][5][1<<4];
pair<int64,int> solve(int64 mid){
for(int i=0;i<=m;++i) fill(f[0][i],f[0][i]+(1<<m),inf);
f[0][m][(1<<m)-1]=g[0][m][(1<<m)-1]=0;
int o=1;
for(int u=1;u<=n;++u){
for(int i=0;i<=m;++i) fill(f[o][i],f[o][i]+(1<<m),inf);
copy(f[o^1][m],f[o^1][m]+(1<<m),f[o][0]);
copy(g[o^1][m],g[o^1][m]+(1<<m),g[o][0]);
for(int i=0;i<m;++i)for(int s=0;s<1<<m;++s){
if(i<m-1){
int t=s|1<<i|1<<(i+1);
int64 v=f[o][i][s]+B[u][i]-mid;
int c=g[o][i][s]+1;
if(f[o][i+2][t]>v or (f[o][i+2][t]==v and g[o][i+2][t]<c))
f[o][i+2][t]=v,g[o][i+2][t]=c;
}
if(u>1 and ~s>>i&1){
int t=s|1<<i;
int64 v=f[o][i][s]+A[u-1][i]-mid;
int c=g[o][i][s]+1;
if(f[o][i+1][t]>v or (f[o][i+1][t]==v and g[o][i+1][t]<c))
f[o][i+1][t]=v,g[o][i+1][t]=c;
}
int t=s&~(1<<i);
int64 v=f[o][i][s];
int c=g[o][i][s];
if(f[o][i+1][t]>v or (f[o][i+1][t]==v and g[o][i+1][t]<c))
f[o][i+1][t]=v,g[o][i+1][t]=c;
}
o^=1;
}
int64 ans=inf;int K=0;
for(int s=0;s<1<<m;++s)
if(ans>f[o^1][m][s] or (ans==f[o^1][m][s] and K<g[o^1][m][s]))
ans=f[o^1][m][s],K=g[o^1][m][s];
return make_pair(ans,K);
}
void real_main(){
read(n),read(m);
int K=read<int>();
for(int i=1;i<n;++i)for(int j=0;j<m;++j) read(A[i][j]);
for(int i=1;i<=n;++i)for(int j=0;j<m-1;++j) read(B[i][j]);
int64 l=0,r=1e14;
while(l<r){
int64 mid=(l+r)>>1;
if(solve(mid).second>=K) r=mid;
else l=mid+1;
}
printf("%lld
",solve(l).first+l*K);
}
int main(){
for(int T=read<int>();T--;) real_main();
return 0;
}
Jiry Matchings
给一棵边权树，(f(i)) 表示 (i) 条边的最大匹配。求出 (f(1),f(2),dots,f(n-1))。
(n leq 2 imes 10^5)，时限6s。
费用流
这是个二分图最大权匹配的问题，有经典费用流算法。
CO int N=2e5+10;
namespace flow{
int n,S,T;
struct edge {int v,c,w,a;};
vector<edge> to[N];
int64 dis[N];int vis[N];
IN void init(int n){
flow::n=n,S=n-1,T=n;
}
IN void link(int u,int v,int c,int w){
to[u].push_back({v,c,w}),to[v].push_back({u,0,-w});
to[u].back().a=to[v].size()-1,to[v].back().a=to[u].size()-1;
}
bool bfs(){
fill(dis+1,dis+n+1,-1e18),dis[T]=0;
deque<int> Q={T};vis[T]=1;
while(Q.size()){
int u=Q.front();
Q.pop_front(),vis[u]=0;
for(CO edge&e:to[u])if(to[e.v][e.a].c and dis[e.v]<dis[u]-e.w){
dis[e.v]=dis[u]-e.w;
if(vis[e.v]) continue;
if(Q.size() and dis[e.v]>=dis[Q.front()]) Q.push_front(e.v);
else Q.push_back(e.v);
vis[e.v]=1;
}
}
return dis[S]>-1e18;
}
int dfs(int u,int lim){
if(u==T) return lim;
vis[u]=1;
int rest=lim;
for(edge&e:to[u])if(!vis[e.v] and e.c and dis[e.v]==dis[u]-e.w){
int delta=dfs(e.v,min(e.c,rest));
if(!delta) {dis[e.v]=-1e18;continue;}
rest-=delta,e.c-=delta,to[e.v][e.a].c+=delta;
if(!rest) break;
}
vis[u]=0;
return lim-rest;
}
vector<int64> main(){
vector<int64> ans={0};
while(bfs()){
int len=dfs(S,1e9);
for(int i=1;i<=len;++i) ans.push_back(dis[S]);
}
for(int i=1;i<(int)ans.size();++i) ans[i]+=ans[i-1];
return ans;
}
}
struct edge {int v,w;};
vector<edge> to[N];
void dfs(int u,int fa,int dep){
if(dep&1) flow::link(u,flow::T,1,0);
else flow::link(flow::S,u,1,0);
for(CO edge&e:to[u])if(e.v!=fa){
if(dep&1) flow::link(e.v,u,1,e.w);
else flow::link(u,e.v,1,e.w);
dfs(e.v,u,dep+1);
}
}
int main(){
int n=read<int>();
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>(),w=read<int>();
to[u].push_back({v,w}),to[v].push_back({u,w});
}
flow::init(n+2);
dfs(1,0,0);
vector<int64> ans=flow::main();
for(int i=1;i<(int)ans.size();++i) printf("%lld%c",ans[i],"
"[i==n-1]);
for(int i=ans.size();i<n;++i) printf("?%c","
"[i==n-1]);
return 0;
}
整体带权二分
可以用费用流解决说明这个 (f(i)) 是个上凸函数。那么尝试用带权二分+整体二分解决。
https://www.mina.moe/archives/6349
现在我们就可以说明第一个问题：我们是否可能无法找到恰好 k 段的情况。
如果函数图像存在共线的三点，那么中间的那个点往往取不到。因为无论如何一条直线都不会与那个点相切。因此那个点横坐标代表的段数是永远取不到的。不过，如果我们找到了与他共线的那些点的最左边的点，我们就可以通过左边那个点直接推出他的答案，因此这个问题解决了。
struct node {int128 x;int y;};
IN bool operator<(CO node&a,CO node&b){
return a.x!=b.x?a.x<b.x:a.y>b.y; // as few as possible
}
IN node operator+(CO node&a,CO node&b){
return {a.x+b.x,a.y+b.y};
}
CO int N=2e5+10;
struct edge {int v,w;};
vector<edge> to[N];
int cnt[N][2],que[N];
void dfs(int u,int fa){
cnt[u][0]=cnt[u][1]=0;
for(int i=0;i<(int)to[u].size();++i){
int v=to[u][i].v;
if(v==fa){
to[u].erase(to[u].begin()+i),--i;
continue;
}
dfs(v,u);
cnt[u][1]+=max(cnt[v][0],cnt[v][1]);
cnt[u][1]=max(cnt[u][1],cnt[u][0]+cnt[v][0]+1);
cnt[u][0]+=max(cnt[v][0],cnt[v][1]);
}
que[++que[0]]=u;
}
node dp[N][2];
void bfs(int128 cost){
for(int i=1;i<=que[0];++i){
int u=que[i];
dp[u][0]=dp[u][1]={0,0};
for(CO edge&e:to[u]){
dp[u][1]=dp[u][1]+max(dp[e.v][0],dp[e.v][1]);
dp[u][1]=max(dp[u][1],dp[u][0]+dp[e.v][0]+(node){e.w-cost,1});
dp[u][0]=dp[u][0]+max(dp[e.v][0],dp[e.v][1]);
}
}
}
int64 ans[N];
void solve(int l,int r,int128 L,int128 R){
if(l>r) return;
if(L==R){
bfs(L);
node res=max(dp[1][0],dp[1][1]);
for(int i=l;i<=r;++i) ans[i]=res.x+L*i;
return;
}
int128 MID=(L+R)>>1;
bfs(MID);
node res=max(dp[1][0],dp[1][1]);
int mid=l;
while(mid<=r and res.y>mid) ++mid;
solve(l,mid-1,MID+1,R);
solve(mid,r,L,MID);
}
int main(){
int n=read<int>();
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>(),w=read<int>();
to[u].push_back({v,w}),to[v].push_back({u,w});
}
dfs(1,0);
int lim=max(cnt[1][0],cnt[1][1]);
solve(1,lim,-2e14,1e9);
for(int i=1;i<=lim;++i) printf("%lld%c",ans[i],"
"[i==n-1]);
for(int i=lim+1;i<n;++i) printf("?%c","
"[i==n-1]);
return 0;
}
然而它TLE了。究其所以然，它的复杂度是假的。因为每次二分的时候 (T(len)=O(n))，所以总时间复杂度 (O(n^2log n))。
重链分治
正确做法是考虑重链分治。
https://blog.csdn.net/Zayin___/article/details/104084068
考虑如何做两个凸函数的max +卷积，可以考虑差分后归并。
再考虑一个经典的树上分治FFT做法，即对轻儿子做分治FFT，对所有重链做分治FFT。把上面那个做法套上去就可以了。
时间复杂度 (O(n log^2 n))。
CO int N=2e5+10;
CO int64 inf=1e18;
struct edge {int v,w;};
vector<edge> to[N];
int fa[N],val[N],siz[N],son[N];
poly f[2][N],g[2][2][N];
poly merge(poly a,poly b){
if(!a.size()) return b;
if(!b.size()) return a;
for(int i=a.size()-1;i>=1;--i) a[i]-=a[i-1];
for(int i=b.size()-1;i>=1;--i) b[i]-=b[i-1];
poly res={a.front()+b.front()};
int l=1,r=1;
while(l<(int)a.size() or r<(int)b.size()){
if(r==(int)b.size() or (l<(int)a.size() and a[l]>b[r]))
res.push_back(a[l]),++l;
else res.push_back(b[r]),++r;
}
for(int i=1;i<(int)res.size();++i) res[i]+=res[i-1];
return res;
}
poly shift(CO poly&a,int64 x){
vector<int64> res={-inf}; // can't choose nothing
for(int i=0;i<(int)a.size();++i) res.push_back(a[i]+x);
return res;
}
poly max(CO poly&a,CO poly&b){
poly res(max(a.size(),b.size()));
for(int i=0;i<(int)res.size();++i)
res[i]=max(i<(int)a.size()?a[i]:-inf,i<(int)b.size()?b[i]:-inf);
return res;
}
void merge_list(int u){
vector<int> s;
for(;u;u=son[u]) s.push_back(u);
for(int i=0;i<(int)s.size();++i)for(int c=0;c<=1;++c){
g[c][c][i]=f[c][s[i]];
g[c][c^1][i]={-inf};
}
for(int len=2;len/2<=(int)s.size();len<<=1)
for(int i=0;i+len/2<(int)s.size();i+=len){
poly res[2][2];
for(int a=0;a<=1;++a)for(int b=0;b<=1;++b)
for(int c=0;c<=1;++c)for(int d=0;d<=1;++d){
poly t=merge(g[a][b][i],g[c][d][i+len/2]);
res[a][d]=max(res[a][d],t);
if(!b and !c){
int _a=a,_d=d;
if(len/2==1) _a=1;
if(len/2==1 or i+len/2==(int)s.size()-1) _d=1;
t=shift(t,val[s[i+len/2]]);
res[_a][_d]=max(res[_a][_d],t);
}
}
for(int a=0;a<=1;++a)for(int b=0;b<=1;++b)
g[a][b][i]=res[a][b];
}
}
poly h[2][N];
void merge_son(int u){
vector<int> s;
for(CO edge&e:to[u])if(e.v!=fa[u] and e.v!=son[u])
s.push_back(e.v);
h[0][0]={0},h[1][0]={-inf};
for(int i=0;i<(int)s.size();++i){
merge_list(s[i]);
h[0][i]={0},h[1][i]={-inf};
for(int a=0;a<=1;++a)for(int b=0;b<=1;++b){
h[0][i]=max(h[0][i],g[a][b][0]);
if(!a) h[1][i]=max(h[1][i],shift(g[a][b][0],val[s[i]]));
}
}
for(int len=2;len/2<=(int)s.size();len<<=1)
for(int i=0;i+len/2<(int)s.size();i+=len){
poly res[2];
for(int a=0;a<=1;++a)for(int b=0;b<=1;++b){
if(a and b) continue;
poly t=merge(h[a][i],h[b][i+len/2]);
res[a|b]=max(res[a|b],t);
}
for(int c=0;c<=1;++c) h[c][i]=res[c];
}
for(int c=0;c<=1;++c) f[c][u]=h[c][0];
}
void dfs(int u){
siz[u]=1;
for(CO edge&e:to[u])if(e.v!=fa[u]){
fa[e.v]=u;
dfs(e.v);
siz[u]+=siz[e.v];
fa[e.v]=u,val[e.v]=e.w;
if(siz[e.v]>siz[son[u]]) son[u]=e.v;
}
merge_son(u);
}
int main(){
int n=read<int>();
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>(),w=read<int>();
to[u].push_back({v,w}),to[v].push_back({u,w});
}
dfs(1);
merge_list(1);
poly res;
for(int a=0;a<=1;++a)for(int b=0;b<=1;++b)
res=max(res,g[a][b][0]);
for(int i=1;i<n;++i){
if(i<(int)res.size()) printf("%lld",res[i]);
else putchar('?');
putchar("
"[i==n-1]);
}
return 0;
}