POJ 3041 Asteroids(匈牙利+邻接表)

时间:2024-10-14 12:07:26

( ̄▽ ̄)"

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std; const int MAXN=505;
int uN; //二分图左边的点集
vector<int> g[MAXN]; //存储矩阵数据
int link[MAXN]; //记录右边的点v在左边的点集uN中所匹配的点x的编号
bool vis[MAXN]; //记录右边的点是否每个点都已被搜索过 bool DFS(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=1;
if(link[v]==-1||DFS(link[v]))
{
link[v]=u;
return true;
}
}
}
return false;
} int hungary()
{
int res=0; //res为最大匹配数=最小点覆盖数
memset(link,-1,sizeof(link)); for(int u=0;u<uN;u++)
{
memset(vis,0,sizeof(vis));
if(DFS(u))
res++; //匹配成功,匹配数+1
}
return res;
} int main()
{
int n,k;
scanf("%d%d",&n,&k);
uN=n;
while(k--)
{
int r,c;
scanf("%d%d",&r,&c);
g[c-1].push_back(r-1); //如果没有-1,WA;
//如果c-1和r-1的位置对调,则需16MS,现只需0MS
}
printf("%d\n",hungary());
return 0;
}