首页 > 代码库 > 【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫 KM算法

【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫 KM算法

2024-09-19 18:51:19   221人阅读

【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫

Description

在一个n*m的棋盘上要放置若干个守卫。对于n行来说，每行必须恰好放置一个横向守卫；同理对于m列来说，每列
必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的，且每个位置最多只能放置一个守卫，一个守卫
不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。

Input

第一行包含两个正整数n,m(2<=n,m<=100000,n*m<=100000)，分别表示棋盘的行数与列数。
接下来n行，每行m个正整数
其中第i行第j列的数w[i][j](1<=w[i][j]<=10^9)表示在第i行第j列放置守卫的代价。

Output

输出一行一个整数，即占领棋盘的最小代价。

Sample Input

3 4
1 3 10 8
2 1 9 2
6 7 4 6

Sample Output

19
HINT
在(1,1),(2,2),(3,1)放置横向守卫，在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。

题解：从来没想过KM的时间复杂度能完虐费用流~

将 行、列 和 格点 分成两个集合，集合间连边，边权就是该格点的费用，然后将边权变成相反数，用KM跑最大匹配，最后再将答案取相反数就行了

考场上写(chao)的zkw费用流被虐暴了

#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long ll;int n,m,now,cnt;ll ans,temp;int va[200010],vb[200010],to[200010],next[200010],head[200010],from[200010];ll la[200010],lb[200010],val[200010];int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}void add(int a,int b,int c){	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;}int dfs(int x){	va[x]=now;	for(int i=head[x];i!=-1;i=next[i])	{		if(vb[to[i]]!=now)		{			if(!(la[x]+lb[to[i]]-val[i]))			{				vb[to[i]]=now;				if(!from[to[i]]||dfs(from[to[i]]))				{					from[to[i]]=x;					return 1;				}			}			else	temp=min(temp,la[x]+lb[to[i]]-val[i]);		}	}	return 0;}int main(){	n=rd(),m=rd();	int i,j,a;	ll b;	memset(head,-1,sizeof(head));	memset(la,0x80,sizeof(la));	for(i=1;i<=n;i++)		for(j=1;j<=m;j++)			a=(i-1)*m+j,b=-rd(),add(i,a,b),la[i]=max(la[i],b),add(j+n,a,b),la[j+n]=max(la[j+n],b);	for(i=1;i<=n+m;i++)	{		while(1)		{			now++;			temp=1ll<<60;			if(dfs(i))	break;			for(j=1;j<=n+m;j++)	if(va[j]==now)	la[j]-=temp;			for(j=1;j<=n*m;j++)	if(vb[j]==now)	lb[j]+=temp;		}	}	for(i=1;i<=n+m;i++)	ans+=la[i];	for(i=1;i<=n*m;i++)	ans+=lb[i];	printf("%lld",-ans);	return 0;}

【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫 KM算法


联系
我们