题面
贝茜想在 \(N\times N\) 的网格中驾驶她的宇宙飞船。网格中有 \(K\) 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。
贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。
对于 \(100\%\) 的数据，\(1 \leq N \leq 500\)，\(1 \leq K \leq N \times N\)。
思路
见到“最小代价”想到最小点覆盖。这道题就是最小点覆盖。竟然可以消除一行或者一列，那么对行建点 \(L(i)\),对列建 \(C(i)\)，然后连边 \((L(i),C(i))\)，不难发现这是一个二分图，直接匈牙利即可。
时间复杂度 \(O(n^2)\)。
代码
#include <iostream>
#include <vector>
using namespace std;
int n,m,t;
int mch[1005],vist[1005];
vector<int> g[1005];
bool dfs(int u,int tag){
if(vist[u]==tag) return false;
vist[u]=tag;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if((mch[v]==0)||dfs(mch[v],tag)){
mch[v]=u;
return true;
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v+n);
}
int ans=0;
for(int i=1;i<=2*n;i++){
if(dfs(i,i)) ans++;
}
cout<<ans<<endl;
return 0;
}