原题链接

还是不会建立二分图啊!!!蒟蒻落泪

想了很久以为是缩点,结果不用缩就是在相邻点处建边就行了(覆盖面积不允许重复！！！)

关键还是建立二分图:

       这道题是将相邻点在不同集合,比如[1,1]在集合1,[1,2]、[0,1]在集合2.通过画图可以发现如果相邻则它们的i+j的奇偶一定不同.因此可以分类进两个集合.

想到怎么建图就容易了

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 610;
 6 int xx[4] = {-1,1,0,0},yy[4] = {0,0,-1,1};
 7 int n,lmp[N][N],rmp[N][N],r,c,match[N*N];
 8 bool g[N][N],st[N*N];
 9 char mp[N][N];
10 void inits()
11 {
12     memset(g,0,sizeof g); memset(lmp,0,sizeof lmp);
13     memset(rmp,0,sizeof rmp); memset(match,-1,sizeof match);
14     r = 0,c = 0;
15 }
16 bool dfs(int x)
17 {
18     for(int i=1;i<=c;i++)
19     {
20         if(!g[x][i]||st[i]) continue;
21         st[i] = 1;
22         if(match[i]==-1||dfs(match[i]))
23         {
24             match[i] = x;
25             return true;
26         }
27     }
28     return false;
29 }
30 int main()
31 {
32     freopen("in.txt","r",stdin);
33     int T,kcase = 0;
34     scanf("%d",&T);
35     while(T--)
36     {
37         inits();
38         int res = 0;
39         scanf("%d",&n);
40         for(int i=0;i<n;i++) scanf("%s",mp[i]);
41         for(int i=0;i<n;i++)
42         {
43             for(int j=0;j<n;j++)
44             {
45                 if(mp[i][j]=='#')
46                 {
47                     if((i+j)&1) lmp[i][j] = ++r;
48                     else rmp[i][j] = ++c;
49                 }
50             }
51         }
52         for(int i=0;i<n;i++)
53             for(int j=0;j<n;j++)
54                 if(lmp[i][j])
55                 {
56                     for(int k=0;k<4;k++)
57                     {
58                         int dx = i+xx[k],dy = j+yy[k];
59                         if(dx>=0&&dx<n&&dy>=0&&dy<n&&rmp[dx][dy])
60                             g[lmp[i][j]][rmp[dx][dy]] = 1;
61                     }
62                 }
63         for(int i=1;i<=r;i++)
64         {
65             memset(st,0,sizeof st);
66             if(dfs(i)) res++;
67         }
68         printf("Case %d: %d\n",++kcase,res);
69     }
70     return 0;
71 }