在一个n*m的草地上，.代表草地，*代表水，现在要用宽度为1，长度不限的木板盖住水，

木板可以重叠，但是所有的草地都不能被木板覆盖。

问至少需要的木板数。

 

这类题的建图方法：

把矩阵作为一个二分图，以行列分别作为2个顶点集

首先以每一行来看，把这一行里面连续的*编号，作为一个顶点

再以每一列来看，把这一列里面连续的*编号，作为一个顶点

则每一个*都有2个编号，以行看时有一个，以列看时有一个，则把这2个编号连边，容量为1

再建一个源点，连接所有行的编号，一个汇点，连接所有列的编号

 

这道题要求的是，所有*都被覆盖，即找到一个顶点的集合S，使得任意边都有至少一个顶点属于

S,即求一个点集顶点覆盖S，又要木板数最少，所以求的就是最小顶点覆盖。

 

最小顶点覆盖怎么求？

二分图中，有：

最小顶点覆盖=最大匹配

 

所以这道题就转化为求二分图的最大匹配了

再转化为最大流dinic算法。

 

 

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5   6 using namespace std;  7   8 const int maxn=2510;  9 const int inf=0x3f3f3f3f; 10 const int s=0; 11 int t; 12 int tota; 13 int totb; 14  15 inline int min(int x,int y) 16 { 17     return x
          
           edge[maxn]; 25 int iter[maxn]; 26 int level[maxn]; 27 char str[55][55]; 28 int hash[55][55]; 29  30 void addedge(int from,int to,int cap) 31 { 32     edge[from].push_back((Edge){to,cap,edge[to].size()}); 33     edge[to].push_back((Edge){
    from,0,edge[from].size()-1}); 34 } 35  36 void build_graph(int n,int m) 37 { 38     for(int i=0;i
           

que; 89 while(!que.empty()) 90 que.pop(); 91 que.push(s); 92 level[s]=1; 93 while(!que.empty()) 94 { 95 int u=que.front(); 96 que.pop(); 97 for(int i=0;i

0&&level[e.to]<0)101 {102 level[e.to]=level[u]+1;103 que.push(e.to);104 }105 }106 }107 }108 109 int dfs(int u,int f)110 {111 if(u==t)112 return f;113 for(int &i=iter[u];i

0&&level[e.to]>level[u])117 {118 int d=dfs(e.to,min(f,e.cap));119 if(d>0)120 {121 e.cap-=d;122 edge[e.to][e.rev].cap+=d;123 return d;124 }125 126 }127 }128 return 0;129 }130 131 int solve()132 {133 int flow=0;134 while(true)135 {136 bfs();137 if(level[t]<0)138 return flow;139 memset(iter,0,sizeof iter);140 int f;141 while(f=dfs(s,inf))142 {143 flow+=f;144 }145 }146 }147 148 int main()149 {150 int n,m;151 while(~scanf("%d%d",&n,&m))152 {153 for(int i=1;i<=n;i++)154 {155 scanf("%s",str[i]+1);156 }157 build_graph(n,m);158 printf("%d\n",solve());159 }160 return 0;161 }