mxqz 二分图最大匹配
查看原帖
mxqz 二分图最大匹配
358739
BFSDFS123楼主2023/1/2 15:48

RT。

不知道为什么就是 Wrong on Test #1,不知道有什么错,恳请大佬帮忙找错

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define eps 1e-8
const int inf=0x3f3f3f3f;
const int Maxn=1010;
const int Maxm=1e6+10;
bool vis[Maxn];
int Maxh[Maxn],Maxl[Maxn];
int mp[Maxn][Maxn];
struct Edge{
	int to;
	int nxt;
}E[Maxm<<1];
int head[Maxn],tot;
void addedge(int u,int v)
{
	tot++;
	E[tot].to=v;
	E[tot].nxt=head[u];
	head[u]=tot;
}
int rmatch[Maxn];
bool dfs(int u)
{
	for(int i=head[u];i;i=E[i].nxt)
	{
		int v=E[i].to;
		if(vis[v]) continue;
		vis[v]=1;
		if(rmatch[v]==-1 || dfs(v))
		{
			rmatch[v]=u;
			return true;
		}
	}
	return false;
}
int n,m;
signed main()
{
	while(~scanf("%lld%lld",&n,&m))
	{
		memset(rmatch,-1,sizeof(rmatch));
		memset(mp,0,sizeof(mp)); 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%lld",&mp[i][j]);
			}
		}
		memset(Maxh,0,sizeof(Maxh));
		memset(Maxl,0,sizeof(Maxl));
		memset(head,0,sizeof(head));
		tot=0;
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				Maxh[i]=max(Maxh[i],mp[i][j]);
				Maxl[j]=max(Maxl[j],mp[i][j]);
				if(mp[i][j]>0)
				{
					sum+=mp[i][j]-1;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(Maxh[i])
			{
				sum=sum-Maxh[i]+1;
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(Maxl[i])
			{
				sum=sum-Maxl[i]+1;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(Maxh[i]==Maxl[j] && mp[i][j])
				{
					addedge(i,j+n);
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i))
			{
				sum+=Maxh[i]-1;
			}
		}
	    printf("%lld\n",sum);  
	}
	return 0;
}

2023/1/2 15:48
加载中...