? 　　?最小點覆蓋概念：選取最小的點數覆蓋二分圖中的所有邊。

　　　最小點覆蓋 = 最大匹配數。

　　　證明：首先假設我們求的最大匹配數為m，那么最小點覆蓋必然 >= m,因為僅僅是這m條邊就至少需要m個點。然后假如我們已經求得最小覆蓋點集，那么在點集中每個點必然有著這樣的性質，在于它相連的邊里面，一定有一條邊的端點不在最小點集中，因為如果連一條這樣的邊都沒有，那這個點完全沒有在最小點集的必要，我們任意選取這樣的一條邊，一定可以形成一個匹配，匹配數與最小點集中的點的個數相等，但現在這僅僅是一個匹配，他必然小于最大匹配，所以最小點覆蓋 <= m，綜上所述，最小點覆蓋 = 最大匹配數，證明成立。

　　　ps：這個證明是我從網上看明白后總結出來的，個人感覺學姐的證明過于籠統，所以就放在了這里，感覺這個更加嚴密易懂（學知識要學明白嘛～）。

　　　代碼如下：實現方法：基礎匈牙利算法。

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1510 int n; struct EDGE {int to,nxt; } edge[10*maxn]; int head[maxn],vis[maxn],match[maxn],tot; void add_edge(int u,int v) {edge[tot].to = v;edge[tot].nxt = head[u];head[u] = tot++; } bool Find(int u) {for(int i = head[u]; i != -1; i = edge[i].nxt){int v = edge[i].to;if(!vis[v]){vis[v] = 1;if(match[v] == -1 || Find(match[v])){match[v] = u;return true;}}}return false; } int slove() {memset(match,-1,sizeof(match));int ans = 0;for(int i = 0; i < n; i++){memset(vis,0,sizeof(vis));if(Find(i))ans++;}return ans; } int main() {int num,a,b,t;while(~scanf("%d",&t)){n = t;memset(head,-1,sizeof(head));tot = 0;while(t--){scanf("%d:(%d)",&a,&num);for(int i = 0;i < num;i++){scanf("%d",&b);add_edge(a,b);add_edge(b,a);}}int ans = slove()/2;printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/jifahu/p/5521112.html

總結

以上是生活随笔為你收集整理的HDU 1054 Strategic Game 最小点覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。