数据水了。
显然,匈牙利算法不能跑两遍取按位与。
然而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;
}