題目鏈接

---

二分圖一個很重要的定理：看了很多大神的博客表示看不懂為什么，以后再看

最小點覆蓋=最大匹配

最小點覆蓋就是在二分圖里邊，選擇一個點，將所有與該點相鏈接的邊刪去，問最小找多少個點能夠把所有的邊刪去。

本題的思路：將每一個點的坐標（x,y）轉(zhuǎn)化為一條邊左側(cè)的點x到右側(cè)的一個點y，x，y之間存在一條邊。

那么你不管刪除那一個點，將該點對應(yīng)的邊全部刪去，就對應(yīng)上邊最小點的定義，與此同時，刪去左邊的點相當于將那一點對應(yīng)行的所有點刪除，刪去右邊的點相當與對應(yīng)點所在的列刪除，又對于了題意，所以就轉(zhuǎn)化為了一個裸的最小點覆蓋

然后匈牙利算法求最大匹配即可,代碼如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=505;
int mp[maxn][maxn],used[maxn],girl[maxn];
int n,m;
int find(int u)
{for(int i=1;i<=n;i++){if(mp[u][i]&&!used[i]){used[i]=1;if(girl[i]==-1||find(girl[i])){girl[i]=u;return 1;}}}return 0;
}
int hungry()
{memset(girl,-1,sizeof(girl));int ans=0;for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(find(i)) ans++;}return ans;
}
int main()
{int x,y;while(cin>>n>>m){memset(mp,0,sizeof(mp));for(int i=1;i<=m;i++)scanf("%d %d",&x,&y),mp[x][y]=1;printf("%d\n",hungry());}return 0;
}

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3041 Asteroids 二分图最小点覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。