题目传送门：POJ 3020

题意就是用圈来圈，求用多少圈能把圈完。

属于最大独立集问题，开始不知道这个，想了半天Orz。

最大独立集的定义是图中两两互不相邻的顶点构成的集合。

有个结论是最大独立集+最小覆盖集=V，而最小覆盖集=最大匹配，所以我们可匈牙利算法来做这个题。

V = 所有两点组合成的独立集 = 2 （的总数)

又因为（i,j） = （j,i）匹配

（2 （的总数） - 最大匹配数） / 2 = *的总数 - 最大匹配数/2

据说状态压缩DP和带花树也可以做这道题，之后试试～

###Code

POJ 3020
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 50

char rec[MAXN][MAXN];
bool g[MAXN*MAXN][MAXN*MAXN];
bool b[MAXN*MAXN];
int h, w, ans, total;
int mylink[MAXN*MAXN];
int r[4][2] = {
    {0, 1}, 
    {0, -1}, 
    {1, 0}, 
    {-1, 0}
};

bool find(int a)
{
	for(int i = 0; i < h * w; i++)
	{
		if(g[a][i] == true && !b[i])
		{
			b[i] = true;
			if(mylink[i] == 0 || find(mylink[i]) )
			{
				mylink[i] = a;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int cas, total;
	scanf("%d", &cas);
	while(cas --)
	{
		memset(g, false, sizeof(g));
		memset(mylink, 0, sizeof(mylink));
		total = ans = 0;
		scanf("%d%d", &h, &w);
		getchar();
		for(int i = 0; i < h; i++)
		{
			for(int j = 0; j < w; j++)
			{
				rec[i][j] = getchar();
				if(rec[i][j] == '*') total++;
			}
			getchar();
		}
		for(int i = 0; i < h; i++)
			for(int j = 0;  j < w; j++)
				for(int k = 0; k < 4; k++)
				{
					int xx = i + r[k][0];
					int yy = j + r[k][1];
					if(rec[i][j] == '*' && rec[xx][yy] == '*' &&  xx >= 0 && yy >= 0 && xx < h && yy < w)
						g[i * w + j][xx * w + yy] = g[xx * w +yy][i * w + j] = true;
				}
		for(int i = 0; i < h * w; i++)
		{
			memset(b, false, sizeof(b));
			if(find(i)) ans++;
		}
		ans /= 2;
		printf("%d\n", total - ans);
	}
    return 0;
}