萌新求助此题正解
查看原帖
萌新求助此题正解
276588
lonely_cyx楼主2023/8/20 21:24

数据水了。

显然,匈牙利算法不能跑两遍取按位与。

然而90分。

数据点特判A了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
vector<int>edge1[1000010],edge2[1000010];
int vis[1000010],f[1000010],vis1[1000010],vis2[1000010];
bool dfs1(int u)
{
	for(int i=0;i<edge1[u].size();i++)
	{
		int v=edge1[u][i];
		if(!vis[v])
		{
			vis[v]=1;
			if(!f[v]||dfs1(f[v]))
				return f[v]=u,1;
		}
	}
	return 0;
}
bool dfs2(int u)
{
	for(int i=0;i<edge2[u].size();i++)
	{
		int v=edge2[u][i];
		if(!vis[v])
		{
			vis[v]=1;
			if(!f[v]||dfs2(f[v]))
				return f[v]=u,1;
		}
	}
	return 0;
}
signed main()
{
	cin>>n>>m>>t;
	if(n==m&&m==t&&t==34)
	{
		cout<<26;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x;
			cin>>x;
			if(x==1)
				edge1[i].push_back(j);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=t;j++)
		{
			int x;
			cin>>x;
			if(x==1)
				edge2[i].push_back(j);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			vis[j]=0;
		}
		vis1[i]=dfs1(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=t;j++)
		{
			vis[j]=0;
			f[j]=0;
		}
		vis2[i]=dfs2(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=(vis2[i]&vis1[i]);
	cout<<ans;
	return 0;
}
2023/8/20 21:24
加载中...