題意：
? ? ? 給你一些點(diǎn)，和一些邊，如果把一個(gè)點(diǎn)安裝保護(hù)裝置，那么與他直接相連的點(diǎn)就可以被保護(hù)，題目問的是最少安裝多少個(gè)點(diǎn)能讓所有的點(diǎn)都被保護(hù)。

思路：

? ? ? 這是最基礎(chǔ)的二分圖最少定點(diǎn)覆蓋，對于可以保護(hù)的點(diǎn)，我們只要找到最大的匹配次數(shù)，也就是最少的安置個(gè)數(shù)就行了，直接一遍匈牙利，注意的一點(diǎn)是建圖的時(shí)候記得建雙向邊，最后答案要除以2，因?yàn)閍->b b->a 匹配數(shù)是2。

#include<stdio.h> #include<string.h>#define N_node 1550 #define N_edge 2255000 typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mk_dfs[N_node] ,mk_gx[N_node];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int DFS_XYL(int x) {for(int k = list[x] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = x;return 1;}}return 0; }int main () {int n ,i ,ans ,nn ,from ,to;while(~scanf("%d" ,&n)){memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= n ;i ++){scanf("%d:(%d)" ,&from ,&nn);while(nn--){scanf("%d" ,&to);add(from + 1 ,to + 1);add(to + 1 ,from + 1);}}memset(mk_gx ,255 ,sizeof(mk_gx));ans = 0;for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));ans += DFS_XYL(i);}printf("%d\n" ,ans / 2);}return 0; }

總結(jié)

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

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