Hlg 1407 【最小点权覆盖】.cpp

题意:

给出一个图该图的每个格子上有值

当扫射一行或一列的时候格子上的值非0的就-1

输入：

　　给出n m 表示该图为n*m的图

　　接下来n*m的图写上格子的值

输出：

　　最少扫射几次可以使所有点权变成0

思路：

　　假使行为Ui 边为Vi

　　则题目可以看成求 Ui+Vj>=Wij

　　把边看成点把点看成边

　　所以用最小点权匹配..

　　因为n 和 m是不一定的~所以把该二分图补点..

<所谓补点....就是....v = max(n, m)>

Tips：

　　最小点权覆盖 = 最大边权匹配

　　如果要求最大点权覆盖则把图变为负值

　　然后求总值的时候该 res -= G[link[i]][i];

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <cmath>
 4 #define M 210
 5 const int INF = 0x1f1f1f1f;
 6 
 7 int v;
 8 int link[M], lx[M], ly[M];
 9 int visx[M], visy[M], G[M][M];
10 int slack;
11 int DFS(int x)
12 {
13     visx[x] = 1;
14     for (int y = 1;y <= v; ++y)
15     {
16         if (visy[y])
17             continue;
18         int t = lx[x] + ly[y] - G[x][y];
19         if (t == 0)
20         {
21             visy[y] = 1;
22             if (link[y] == -1||DFS(link[y]))
23             {
24                 link[y] = x;
25                 return 1;
26             }
27         }
28         else if (slack > t)
29             slack = t;
30     }
31     return 0;
32 }
33 int KM()
34 {
35     int i,j;
36     memset (link,-1,sizeof(link));
37     memset (ly,0,sizeof(ly));
38 
39     for (i = 1;i <= v;i ++)
40         for (j = 1,lx[i] = -INF;j <= v; ++j)
41             if (G[i][j] > lx[i])
42                 lx[i] = G[i][j];
43 
44     for (int x = 1;x <= v; ++x)
45     {
46         memset(visx,0,sizeof(visx));
47         memset(visy,0,sizeof(visy));
48         while (1)
49         {
50             slack=INF;
51             if (DFS(x))
52                 break;
53             for(i = 1; i <= v; i++)
54             {
55                 if(visx[i]) {  lx[i]-=slack;  visx[i]=0;  }
56                 if(visy[i]) {  ly[i]+=slack;  visy[i]=0;  }
57             }
58 
59         }
60     }
61     int res = 0;
62     for (i = 1;i <= v;i ++)
63         if (link[i] > -1)
64             res += G[link[i]][i];
65     return res;
66 }
67 
68 int main()
69 {
70     int i, j, k;
71     int n, m;
72     while(scanf("%d %d", &n, &m) != EOF)
73     {
74         memset(G, 0, sizeof(G));
75         for(i = 1; i <= n; ++i)
76         for(j = 1; j <= m; ++j) {
77             scanf("%d", &G[i][j]);
78         }
79 
80         if(n < m)
81          n = m;
82         v = n;
83 
84         int ans = KM();
85         printf("%d\n", ans);
86     }
87     return 0;
88 }

题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1407