[bzoj1735]泥泞的牧场

亦凉 2021-11-17 15:36 168阅读 0赞

考虑木板一定都尽量长，对于每一个污泥，最多只有两种木板会覆盖它（横着和竖的），将这两块木板连边，意味着每一条边两端端点中一定有一个点要被选，即最小点覆盖=最大匹配数。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 105
     4 struct ji{
     5     int nex,to;
     6 }edge[N*N];
     7 int E,n,m,t,ans,head[N*N],id[N][N],vis[N*N],flag[N*N];
     8 char s[N][N];
     9 void add(int x,int y){
    10     edge[E].nex=head[x];
    11     edge[E].to=y;
    12     head[x]=E++;
    13 }
    14 bool dfs(int k){
    15     if (vis[k])return 0;
    16     vis[k]=1;
    17     for(int i=head[k];i!=-1;i=edge[i].nex){
    18         int v=edge[i].to;
    19         if ((!flag[v])||(dfs(flag[v]))){
    20             flag[k]=v;
    21             flag[v]=k;
    22             return 1;
    23         }
    24     }
    25     return 0;
    26 }
    27 int main(){
    28     scanf("%d%d",&n,&m);
    29     for(int i=0;i<n;i++,t++){
    30         scanf("%s",s[i]);
    31         for(int j=0;j<m;j++)
    32             if (s[i][j]=='*')id[i][j]=t;
    33             else t++;
    34     }
    35     memset(head,-1,sizeof(head));
    36     for(int j=0;j<m;j++,t++)
    37         for(int i=0;i<n;i++)
    38             if (s[i][j]=='*')add(t,id[i][j]);
    39             else t++;
    40     for(int i=0;i<n;i++)
    41         for(int j=0;j<m;j++)t=max(t,id[i][j]);
    42     for(int i=1;i<=t;i++){
    43         memset(vis,0,sizeof(vis));
    44         if (!flag[i])ans+=dfs(i);
    45     }
    46     printf("%d",ans);
    47 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249612.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/37481a15bbca427d8fdad4d231717002.png

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关 BZOJ2938

BZOJ2938-病毒题意： > 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们...

偏执的太偏执、/ 2024年04月20日 10:24/ 0 赞/ 75 阅读

相关 1号牧场风光互补供电系统设计

目录 1.风光互补发电系统概述 7 1.1 可再生能源开发应用 7 1.2 风能资源现状 8 1.3 太阳能资源现状 10 1.4 风光互补供电系统的优缺

小灰灰/ 2024年04月03日 11:12/ 0 赞/ 54 阅读

相关修理牧场（25 分）

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自

爱被打了一巴掌/ 2022年05月09日 02:38/ 0 赞/ 239 阅读

相关 PTA 数据结构修理牧场

7-8 修理牧场（25 分）农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头

冷不防/ 2022年04月22日 11:06/ 0 赞/ 205 阅读

相关 bzoj3632

裸的最大团，随机化大法好多次随机出一个选择顺序然后贪心即可 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

心已赠人/ 2021年12月23日 07:39/ 0 赞/ 155 阅读

相关 bzoj4042

比较好的树形dp，涉及到树上路径的题目，我们往往考虑对路径分类当我们考虑以x为根的子树，有这样几类路径 1. 起点终点都在子树内 2. 一个点延伸到子树外对于要选择

ゝ一世哀愁。/ 2021年12月23日 07:37/ 0 赞/ 132 阅读

相关 bzoj 1834

网络流的模板题首先第一问我们直接用dinic搞就行了，费用直接存为0（时间上界非常松，这道题是能过），然后第二问我们只需要在第一问的残余网络上加一个源点，源点指向1号点

灰太狼/ 2021年12月20日 14:51/ 0 赞/ 236 阅读

相关 BZOJ 3166

BZOJ3196: Tyvj 1730 二逼平衡树传送门：[https://www.lydsy.com/JudgeOnline/problem.php?id=3196]

太过爱你忘了你带给我的痛/ 2021年12月04日 06:59/ 0 赞/ 238 阅读

相关 [bzoj1735]泥泞的牧场

考虑木板一定都尽量长，对于每一个污泥，最多只有两种木板会覆盖它（横着和竖的），将这两块木板连边，意味着每一条边两端端点中一定有一个点要被选，即最小点覆盖=最大匹配数。 ![C

亦凉/ 2021年11月17日 15:36/ 0 赞/ 169 阅读

相关 bzoj4407

以前写过一次线性筛发现不是很理解写了个欧拉筛的 t了其实每次推式子，都会先推出一组的

红太狼/ 2021年01月08日 13:38/ 0 赞/ 375 阅读