文档章节

ICPC Pacific Northwest Regional Contest 2016 Maximum Islands(二分图最大独立集)

o
 osc_mpdswsal
发布于 07/01 11:48
字数 751
阅读 18
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Maximum Islands

思路:预处理‘L’周围包围‘W’。‘L’独自成为岛屿为最优,我们‘L’,‘W’交替处理的图((x+y)%2为同一个集合),分为两个集合,相邻的‘L’和‘W’有边,同一个集合没边,变成二分图的最大独立集问题,得出最多的互不相邻的点就是最大岛屿数量。因为我们匹配的出发点是全图,所以匹配数 = match / 2。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <vector>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 const int N = 50;
 10 int mv_x[] = {1, -1, 0, 0};
 11 int mv_y[] = {0, 0, 1, -1};
 12 char mp[N][N]; //地图
 13 vector<int > E[N * N]; //
 14 int pre[N * N]; 
 15 bool vis[N * N];
 16 bool viss[N][N]; //是否访问过
 17 bool e[N * N][N * N]; //重复边判定
 18 int id[N][N]; //编号
 19 int n, m, island, poi;
 20 
 21 inline bool check(int x, int y)
 22 {
 23     return x >= 0 && x < n && y >= 0 && y < m;
 24 }
 25 
 26 void dfs_island(int x, int y)
 27 {
 28     mp[x][y] = 'W';
 29     for(int p = 0; p < 4; ++p){
 30         int dx = x + mv_x[p];
 31         int dy = y + mv_y[p];
 32 
 33         if(check(dx, dy) && mp[dx][dy] == 'L'){
 34             dfs_island(dx, dy);
 35         }
 36     }
 37 }
 38 
 39 inline void add(int u, int v)
 40 {
 41     E[u].push_back(v);
 42     E[v].push_back(u);
 43 }
 44 
 45 void dfs_cloud(int x, int y)
 46 {
 47     viss[x][y] = 1;
 48     for(int p = 0; p < 4; ++p){
 49         int dx = x + mv_x[p];
 50         int dy = y + mv_y[p];
 51 
 52         if(check(dx, dy) && mp[dx][dy] == 'C'){
 53             int id1 = min(id[x][y], id[dx][dy]);
 54             int id2 = max(id[x][y], id[dx][dy]);
 55             if(e[id1][id2] == 0){
 56                 e[id1][id2] = 1;
 57                 add(id1, id2);
 58             }
 59             if(!viss[dx][dy]){
 60                 viss[dx][dy] = 1;
 61                 dfs_cloud(dx, dy);
 62             }      
 63         }
 64     }
 65 }
 66 
 67 bool find(int u)
 68 {
 69     for(auto v : E[u]){
 70         if(vis[v]) continue;
 71         vis[v] = 1;
 72         if(!pre[v] || find(pre[v])){
 73             pre[v] = u;
 74             return true;
 75         }
 76     }
 77     return false;
 78 }
 79 
 80 void show()
 81 {
 82     for(int i = 0; i < n; ++i){
 83         for(int j = 0; j < m; ++j){
 84             cout << mp[i][j];
 85         }cout << endl;
 86     }
 87 }
 88 
 89 void solve()
 90 {
 91 
 92     scanf("%d%d", &n, &m);
 93     for(int i = 0; i < n; ++i) scanf("%s", &mp[i]);
 94     //预处理L
 95     for(int i = 0; i < n; ++i){
 96         for(int j = 0; j < m; ++j){
 97             if(mp[i][j] == 'L'){
 98                 for(int p = 0; p < 4; ++p){
 99                     int dx = i + mv_x[p];
100                     int dy = j + mv_y[p];
101                     if(check(dx, dy) && mp[dx][dy] == 'C'){
102                         mp[dx][dy] = 'W';
103                     }
104                 }
105             }
106         }
107     }
108 
109     //统计岛屿个数,编号
110     for(int i = 0; i < n; ++i){
111         for(int j = 0; j < m; ++j){
112             if(mp[i][j] == 'L'){
113                 island++;
114                 dfs_island(i, j);
115             }else if(mp[i][j] == 'C') id[i][j] = ++poi;
116         }
117     }
118 
119     //建图
120     for(int i = 0; i < n; ++i){
121         for(int j = 0; j < m; ++j){
122             if(mp[i][j] == 'C'){
123                 dfs_cloud(i, j);
124             }
125         }
126     }
127 
128     //匹配
129     int match = 0;
130     for(int i = 0; i < n; ++i){
131         for(int j = 0; j < m; ++j){
132             if(!id[i][j]) continue;
133             for(int x = 1; x <= poi; ++x) vis[x] = 0; 
134             if(find(id[i][j])) match++;
135         }
136     }
137 
138     //printf("island = %d\n", island + poi - match / 2);
139     printf("%d\n", island + poi - match / 2);
140 }
141 
142 
143 int main()
144 {
145 
146     solve();
147 
148     return 0;
149 }

 

o
粉丝 0
博文 72
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Full_of_Boys训练3总结

题目来源: 2016-2017 ACM-ICPC Pacific Northwest Regional Contest E.Enclosure 先计算出内外两个凸包,枚举大凸包上的点,在小凸包上找到两个切点。计算面积时,就相当于删掉几条原先的边,...

osc_jghpf0ob
2018/04/30
2
0
ICPC Pacific Northwest Regional Contest 2016 Maximum Islands(二分图最大独立集)

Maximum Islands 思路:预处理‘L’周围包围‘W’。‘L’独自成为岛屿为最优,我们‘L’,‘W’交替处理的图((x+y)%2为同一个集合),分为两个集合,相邻的‘L’和‘W’有边,同一个集合没边...

osc_xsd7kks3
07/01
4
0
ICPC Pacific Northwest Regional Contest 2016 Maximum Islands(二分图最大独立集)

Maximum Islands 思路:预处理‘L’周围包围‘W’。‘L’独自成为岛屿为最优,我们‘L’,‘W’交替处理的图((x+y)%2为同一个集合),分为两个集合,相邻的‘L’和‘W’有边,同一个集合没边...

SummerMingQAQ
06/30
0
0
ICPC Pacific Northwest Regional Contest 2016 Maximum Islands(二分图最大独立集)

Maximum Islands 思路:预处理‘L’周围包围‘W’。‘L’独自成为岛屿为最优,我们‘L’,‘W’交替处理的图((x+y)%2为同一个集合),分为两个集合,相邻的‘L’和‘W’有边,同一个集合没边...

SummerMingQAQ
06/30
0
0
Deadline队伍训练实录

To do list 畅所欲言 General 一有空就训练 总结技能缺失内容,进行专项训练 及时补锅 训练时紧张起来 学习进度 Ym: 种树需趁早 2018/4/8 ym决定(must)爆肝dp专题(企图获得进步) Czh: 战术...

osc_i9cwf8gz
2018/04/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

测试工程师需要了解的shell变量知识

顾老师安全测试新课,报名地址: http://www.hbz100.com/pc/course/courseInfo.do?courseId=182320200226121405459。疫情期间,您在注意身体安全的同时,关注身体安全了吗?500元工作几天的薪...

啄木鸟顾老师
04/15
13
0
前端面试开源项目清单(github仓库,个人网站都有)

 复习前端面试的知识,是为了巩固前端的基础知识,最重要的还是平时的积累! ” 开源项目 https://github.com/InterviewMap/CS-Interview-Knowledge-Map 建立最好的面试地图。目前的内容包...

Fe-frank
05/11
12
0
【Flutter 专题】33 自定义 View 之 Canvas (一)

和尚最近在学习自定义 View,刚了解了一下 Paint 画笔的神奇之处,现在学习一下 Canvas 画布的神秘之处。Flutter 提供了众多的绘制方法,和尚接触不深,尽量都尝试一下。 Canvas 画布 drawCo...

阿策
2019/02/26
5
0
程序员,有需求做需求,有bug改bug,有什么好生气的呢?

对哦,我有什么好生气的呢! 本文分享自微信公众号 - WriteSimpleDemo(this_is_a_wechat)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入...

PedroQin
2019/10/25
0
0
[从0到1搭建ABP微服务] - 搭建授权服务

一、简介 授权中心是微服务架构中最为核心重要的环节,不仅为web、app等客户端提供身份授权服务,还对其他微服务提供身份认证服务。ABP微服务架构中使用identityServer4框架进行身份管理,并...

osc_g91p39eg
12分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部