HDU 6094 Rikka with K-Match 【wqs二分+轮廓线dp】

HDU 6094 Rikka with K-Match

这不是第一次写wqs二分，只是第一次知道这玩意叫wqs二分（捂脸

$f(i)$ 表示匹配了为 $i$ 条边最小权值，然后发现 $f(i)$ 是向上凸的。

因为 $f(i)$ 也可以表示流量为 $i$ 的最小费用，可以用费用流来表示的都是凸的。

然后就二分斜率 $k$ ，求斜率为 $k$ 时的切点。意思就是每条边的权值 $?k$ ，求合法匹配的最小权值和最小权值对应的匹配的边数 $p$ （多个 $p$ 就取最小的）。如果 $p<$ 我们要求的边数 $num$ ，说明斜率 $k$ 小了，反之同理，二分就行了。

最后要解决的问题就是每条边的权值 $?k$ 之后，怎么求最小权值。因为没有边数的限制了，而且发现 $m\le 4$ ，轮廓线dp即可。

#include <bits/stdc++.h>
#define N 40004
#define MAX 17
using namespace std;
typedef long long ll;
const ll inf=1e17;
int T,n,m,cnt[N][5][MAX],A[N][5][2];//0横着 1竖着
ll k,dp[N][5][MAX];
void updata(int x,int y,int S,int i,int j,int T,ll co,int ad){
    ll v=dp[x][y][S]+co; int cn=cnt[x][y][S]+ad;if(v<dp[i][j][T])dp[i][j][T]=v,cnt[i][j][T]=cn;else if(v==dp[i][j][T]&&cn<cnt[i][j][T]) cnt[i][j][T]=cn;
}
ll mn,p;
bool chk(ll mid){
    int nxt,x,y; mn=inf,p=inf;for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)for(int S=0;S<(1<<(m));S++)dp[i][j][S]=inf,cnt[i][j][S]=80000;for(int j=1;j<=m;j++){
    x=(j>1)?i:(i-1),y=(j>1)?j-1:m;for(int S=0;S<(1<<m);S++){
    if(i!=1&&(!(S&(1<<(j-1)))))nxt=S|(1<<(j-1)),updata(x,y,S,i,j,nxt,1ll*A[i-1][j][1]+mid,1);if(j!=1&&(!(S&(1<<(j-2)))))nxt=(S|(1<<(j-2)))|(1<<(j-1)),updata(x,y,S,i,j,nxt,1ll*A[i][j-1][0]+mid,1);nxt=S; if(nxt&(1<<(j-1))) nxt^=(1<<(j-1));updata(x,y,S,i,j,nxt,0,0);}}}for(int S=0;S<(1<<(m));S++)if(dp[n][m][S]<mn||(dp[n][m][S]==mn&&cnt[n][m][S]<p)) mn=dp[n][m][S],p=cnt[n][m][S];return p<=k;
}
void work(){
    scanf("%d %d %lld",&n,&m,&k);for(int i=1;i<n;i++)for(int j=1;j<=m;j++) scanf("%d",&A[i][j][1]);for(int i=1;i<=n;i++)for(int j=1;j<m;j++) scanf("%d",&A[i][j][0]);ll r=1e14,l=0,mid;while(l<r){
    mid=(l+r)/2+1;if(chk(-mid))l=mid;else r=mid-1;}chk(-l);printf("%lld\n",mn+k*l);
}
int main(){
    
// freopen("test.in","r",stdin);scanf("%d",&T);while(T--) work();
}