[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1741
[算法]
将每颗小行星的行,列相连,问题就转化为了求这张图的最小覆盖
由konig定理可知,最小覆盖 = 最大匹配,因此,用匈牙利算法求二分图最大匹配即可
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 510
#define MAXK 10010 struct edge
{
int to,nxt;
} e[MAXK]; int n,k,i,r,c,ans,tot;
int head[MAXN],match[MAXN << ];
bool visited[MAXN << ]; inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline bool hungary(int u)
{
int i,v;
visited[u] = true;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
visited[v] = true;
if (!match[v] || hungary(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
} int main()
{ scanf("%d%d",&n,&k);
for (i = ; i <= k; i++)
{
scanf("%d%d",&r,&c);
addedge(r,c + n);
}
for (i = ; i <= n; i++)
{
memset(visited,false,sizeof(visited));
if (hungary(i)) ans++;
}
printf("%d\n",ans); return ; }