題目鏈接：點擊查看

題目大意：給出一棵樹，現在要在節點上放置士兵，每個士兵可以監視與其所在的節點直接相連的節點，問最少需要多少個士兵才能將整棵樹都監視到

題目分析：求最少的節點，以保證每條邊都有一個端點在所選節點中，這不就是標準的二分圖的最小點覆蓋，最小點覆蓋等于二分圖最大匹配數，對于這個題目而言我們需要建立無向圖，所以最后答案記得除以2

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;vector<int>node[N];int match[N],vis[N],vis_cnt;bool dfs(int x) {for(auto i:node[x]){if(vis[i]!=vis_cnt){vis[i]=vis_cnt;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }void init() {vis_cnt=1;for(int i=0;i<N;i++)node[i].clear();memset(vis,0,sizeof(vis));memset(match,0,sizeof(match)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF){init();for(int i=1;i<=n;i++){int u,num;scanf("%d:(%d)",&u,&num);u++;while(num--){int v;scanf("%d",&v);v++;node[u].push_back(v);node[v].push_back(u);}}int ans=0;for(int i=1;i<=n;i++,vis_cnt++)if(dfs(i))ans++;printf("%d\n",ans/2);}return 0; }

?

總結

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

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