題意：
? ? ? 給你一個n * n 的矩陣，和X所在的坐標(biāo)，問你最少放多少個**可以把圖里的所有X都覆蓋，每個**可以覆蓋一行，或者一列。


思路：
? ? ? 最小頂點(diǎn)覆蓋，最小頂點(diǎn)覆蓋=二分匹配，每一行最多放一個，每一列最多放一個，對于每一個點(diǎn)，他只要被一行或者一列照應(yīng)就行了。

所以直接把X所在的點(diǎn)的行和列連接在一起，（二分后對于當(dāng)前點(diǎn)相當(dāng)于只選擇一個），這樣最后每個點(diǎn)都會被照應(yīng)到，同時盡可能地去匹配了，也就是盡可能地減少了浪費(fèi)。

#include<stdio.h> #include<string.h>#define N_node 550 #define N_edge 255000typedef 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 ,m ,i;int a ,b;while(~scanf("%d %d" ,&n ,&m)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a ,b);}int sum = 0;memset(mk_gx ,255 ,sizeof(mk_gx));for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));sum += DFS_XYL(i);}printf("%d\n" ,sum);}return 0; }

總結(jié)

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

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