又一个二分图！其实对于这个题，关键是看你怎样建立二分图！
我比较偷懒，就用了一个黑白染色。题目意思很简单，就是要用多少个圆圈完*，当然每个圆只能圈两个*；
具体看代码吧，懒得写了，一个早上，还没吃饭呢？
1 #include <iostream>
2 using namespace std;
3 bool map[500][500];
4 bool vi[500];
5 int link[500];
6 int n,h;
7 int x[4]={0,0,1,-1};
8 int y[4]={1,-1,0,0};
9 bool dfs(int v)
10 {
11 for (int i=1;i<=n;i++)
12 {
13 if (map[v][i]&&!vi[i])
14 {
15 vi[i]=true;
16 if (link[i]==0||dfs(link[i]))
17 {
18 link[i]=v;
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25 int com()
26 {
27 int sum=0;
28 for (int i=1;i<=h;i++)
29 {
30 memset(vi,0,sizeof(vi));
31 if (dfs(i))sum++;
32 }
33 return sum;
34 }
35 int main()
36 {
37 char a[50][16];
38 int b[50][16],c[50][16];
39 int m,k,i,j;
40 int t;
41 cin>>t;
42 while (t--)
43 {
44 cin>>m>>k;
45 n=0,h=0;
46 memset(map,0,sizeof(map));
47 memset(link,0,sizeof(link));
48 memset(b,0,sizeof(b));
49 for (i=1;i<=m;i++)
50 for (j=1;j<=k;j++)
51 {
52 cin>>a[i][j];
53 }
54 h=0,n=0;
55 for (i=1;i<=m;i++)
56 for (j=1;j<=k;j++)
57 if (a[i][j]=='*')
58 {
59 if ((i+j)%2==0)b[i][j]=++h;
60 else b[i][j]=++n;
61 }
62 int dx,dy;
63 for (i=1;i<=m;i++)
64 for (j=1;j<=k;j++)
65 if (a[i][j]=='*'&&(i+j)%2==0)
66 {
67 for (int l=0;l<4;l++)
68 {
69 dx=x[l]+i;
70 dy=y[l]+j;
71 if (a[dx][dy]=='*')
72 map[b[i][j]][b[dx][dy]]=1;
73 }
74 }
75 cout<<h+n-com()<<endl;
76 }
77 return 0;
78 }
79
posted on 2011-04-05 10:46
路修远 阅读(1339)
评论(0) 编辑 收藏 引用 所属分类:
路修远