洛谷P3236 [HNOI2014]画框（最小乘积KM）

题面

传送门

题解

我似乎连\(KM\)都不会打啊→_→

和bzoj2395是一样的，只不过把最小生成树换成\(KM\)了。因为\(KM\)跑的是最大权值所以取个反就行了

//minamoto
#include<bits/stdc++.h>
#define R register
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=105;
struct node{
    int x,y;
    node(){}
    node(R int xx,R int yy):x(xx),y(yy){}
    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
    inline int operator *(const node &b)const{return x*b.y-y*b.x;}
    inline bool operator >(const node &b)const{return x*y>b.x*b.y;}
}ma,mb,res;
int g[N][N],a[N][N],b[N][N],vx[N],vy[N],mt[N],lx[N],ly[N];
int n,d,cnt;
bool dfs(int x){
    vx[x]=cnt;
    fp(y,1,n)if(vy[y]!=cnt)
        if(lx[x]+ly[y]==g[x][y]){
            vy[y]=cnt;
            if(!mt[y]||dfs(mt[y]))return mt[y]=x,true;
        }else cmin(d,lx[x]+ly[y]-g[x][y]);
    return false;
}
node KM(){
    fp(i,1,n)lx[i]=-inf,ly[i]=mt[i]=0;
    fp(i,1,n)fp(j,1,n)cmax(lx[i],g[i][j]);
    fp(x,1,n)while(++cnt,d=inf,!dfs(x)){
        fp(i,1,n){
            if(vx[i]==cnt)lx[i]-=d;
            if(vy[i]==cnt)ly[i]+=d;
        }
    }
    node P(0,0);
    fp(i,1,n)P.x+=a[mt[i]][i],P.y+=b[mt[i]][i];
    return cmin(res,P),P;
}
void solve(node A,node B){
    fp(i,1,n)fp(j,1,n)g[i][j]=-(b[i][j]*(B.x-A.x)-a[i][j]*(B.y-A.y));
    node C=KM();
    if((B-A)*(C-A)>=0)return;
    solve(A,C),solve(C,B);
}
void MAIN(){
    n=read(),res=node(inf,inf);
    fp(i,1,n)fp(j,1,n)a[i][j]=read();
    fp(i,1,n)fp(j,1,n)b[i][j]=read();
    fp(i,1,n)fp(j,1,n)g[i][j]=-a[i][j];
    ma=KM();
    fp(i,1,n)fp(j,1,n)g[i][j]=-b[i][j];
    mb=KM();
    solve(ma,mb);
    printf("%d\n",res.x*res.y);
}
int main(){
//  freopen("testdata.in","r",stdin);
    for(int T=read();T;--T)MAIN();
    return 0;
}

洛谷P3236 [HNOI2014]画框（最小乘积KM）

原文：https://www.cnblogs.com/bztMinamoto/p/10512631.html