[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu

题目链接

题意：

题解：

KM最大权二分图匹配。然后权值的话，左侧原来的 m 个点代表送货员的家，与右侧表示红酒地点的 n 个点之间连边，权值为送货员的家 ni 与红酒处 mi 之间的距离与 mi 到 饭店之间距离的和，选中这条边的话表示这个人直接从家里到红酒处然后把酒送到了饭店。之后在左侧新建 n-1 个点表示走到店里又出来的送货员，其与右侧n个点的权值设为2倍红酒到饭店的距离，因为回到店里之后所有的送货员就没差别了，而且一个人可以被重复利用，没有什么先后的时间限制。n-1 是因为最多就只有 n-1 瓶红酒会被从店里又出来的人送到（至少有 1 个人是直接从家里到红酒处的）。这样直接跑KM就可以了，但是有个问题是原来的KM板子太慢了，到UOJ#80找了个新的板子，能1s跑2000个点的KM。。。

wa点：

• 训练赛时候自己用费用流做题建图假了，注意反向边的意义和边的加入方式。

#include <bits/stdc++.h>
 
using namespace std;
 
#define dbg(x) \
    (void)(cout << "L" << __LINE__ << ":" << #x << " = " << (x) << '\n')
 
//typedef int ll;
typedef long long ll;
const int maxn = 1e4 + 5;
const int maxm = 1e5 + 5;
const int INF = 0x3f3f3f3f;
 
const int N=2007,NPOS=-1;
struct Matrix
{
	int n;
	ll a[N][N];
};
struct KuhnMunkres:Matrix
{
	ll hl[N],hr[N],slk[N];
	int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],ql,qr;
	int check(int i)
	{
		if(vl[i]=1,fl[i]!=NPOS)return vr[q[qr++]=fl[i]]=1;
		while(i!=NPOS)swap(i,fr[fl[i]=pre[i]]);
		return 0;
	}
	void bfs(int s)
	{
		fill(slk,slk+n,INF),fill(vl,vl+n,0),fill(vr,vr+n,0);
		for(vr[q[ql=0]=s]=qr=1;;)
		{
			for(ll d; ql<qr;)
				for(int i=0,j=q[ql++]; i<n; ++i)
					if(!vl[i]&&slk[i]>=(d=hl[i]+hr[j]-a[i][j]))
						if(pre[i]=j,d)slk[i]=d;
						else if(!check(i))return;
			ll d=INF;
			for(int i=0; i<n; ++i)
				if(!vl[i]&&d>slk[i])d=slk[i];
			for(int i=0; i<n; ++i)
			{
				if(vl[i])hl[i]+=d;
				else slk[i]-=d;
				if(vr[i])hr[i]-=d;
			}
			for(int i=0; i<n; ++i)
				if(!vl[i]&&!slk[i]&&!check(i))return;
		}
	}
	void ask()
	{
		fill(fl,fl+n,NPOS),fill(fr,fr+n,NPOS),fill(hr,hr+n,0);
		for(int i=0; i<n; ++i)hl[i]=*max_element(a[i],a[i]+n);
		for(int j=0; j<n; ++j)bfs(j);
	}
} km;
 
int ps[maxn][2];
 
inline int dist(int a, int b)
{
    return abs(ps[a][0] - ps[b][0]) + abs(ps[a][1] - ps[b][1]);
}
 
int main()
{
    int n, m,nx,ny;
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n + m; i++)
    {
        scanf("%d%d", &ps[i][0], &ps[i][1]);
    }
    nx=m+n-1,ny=n;
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            km.a[i][j]=-dist(i+n,j)-dist(j,n+m);
        }
    }
    for(int i=0;i<n-1;++i){
        for(int j=0;j<n;++j){
            km.a[i+m][j]=-2*dist(j,n+m);
        }
    }
    // for(int i=0;i<nx;++i,cout<<endl)
    //     for(int j=0;j<ny;++j) cout<<g[i][j]<<" ";
    km.n=max(nx,ny);
    km.ask();
    int ans=0;
    for(int i=0; i<nx; ++i)ans+=km.a[i][km.fl[i]];
    printf("%d",-ans);
}