POJ-3020 Antenna Placement

题意：给定一张图，上面有很多*。有一些1*2的小纸片，问至少用多少小纸片能覆盖所有的*。

解：翻译一下：每个*看作一个点，两个*之间可以有一条边。问至少选择多少边，能够覆盖所有点。也就是求最小路径覆盖。

二分图最小路径覆盖=所有点个数-最大匹配。

这里很把所有*染色有点麻烦，不如拆点，把所有点拆成一入一出，分成两边，最后除以2。

交了好几发RE，最后怒把数组改成500，过了。poj老爷机名不虚传（）

代码：

 1 #include
 2 #include 
 3 #include <string.h>
 4 #include 
 5 #include 
 6 #include 
 7 using namespace std;
 8 #define ll long long
 9 #define maxx 505
10 #define inf 0x3f
11 const int mod=1e9+7;
12 //#define int long long
13 vector<int> e[maxx];
14 int n,m;
15 int num;
16 int vis[maxx]={0},match[maxx]={0};
17 int mp[maxx][maxx];
18 int xx[4]={0,1,0,-1};
19 int yy[4]={1,0,-1,0};
20 int dfs(int now){
21     for(int i=0;i){
22         int to=e[now][i];
23         if(!vis[to]){
24             vis[to]=1;
25             if(!match[to]||dfs(match[to])){
26                 match[to]=now;
27                 return 1;
28             }
29         }
30     }
31     return 0;
32 }
33 signed main() {
34     int T;
35     cin>>T;
36     char s[maxx];
37     while(T--){
38         num=0;
39         memset(mp,0,sizeof mp);
40         memset(match,0,sizeof match);
41         for(int i=0;i)
42             e[i].clear();
43         cin>>n>>m;
44         for(int i=0;i) {
45             cin>>s;
46             for (int j = 0; j < m; j++)
47                 mp[i][j]=s[j]=='*'?++num:0;
48         }
49         for(int i=0;i)
50             for(int j=0;j){
51                 if(mp[i][j]>0){
52                     for(int k=0;k<4;k++){
53                         int tx=i+xx[k],ty=j+yy[k];
54                         if(tx<0||tx>=n||ty<0||ty>=m)
55                             continue;
56                         if(mp[tx][ty]>0)
57                             e[mp[i][j]].push_back(mp[tx][ty]);
58                     }
59                 }
60             }
61         int ans=0;
62         for(int i=1;i<=num;i++) {
63             memset(vis,0,sizeof vis);
64             if (dfs(i))
65                 ans++;
66         }
67         cout<2<<endl;
68     }
69     return 0;
70 }