文档章节

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

o
 osc_xsd7kks3
发布于 07/01 13:23
字数 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
博文 56
码字总数 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_mpdswsal
07/01
3
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

没有更多内容

加载失败,请刷新页面

加载更多

Kafka如何在千万级别时优化JVM GC问题?

大家都知道Kafka是一个高吞吐的消息队列,是大数据场景首选的消息队列,这种场景就意味着发送单位时间消息的量会特别的大,那既然如此巨大的数据量,kafka是如何支撑起如此庞大的数据量的分发...

hummerstudio
06/18
6
0
我打赌!90%程序员都破解不了这个粽子,不信你试!

放假了 各位读者朋友们,马上就是端午小长假啦,开心激动有木有? 新的故事文章还在创作中,写了初稿感觉不太满意又推倒重来。其实写故事还是挺难的,读者可能第一次第二次有新鲜感,写多了就...

轩辕之风
06/24
30
0
如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

前言 “删库跑路”是程序员经常谈起的话题,今天,我就要教大家如何删!库!跑!路! 开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解...

后端技术漫谈
01/14
30
0
PHP设计模式之代理模式

PHP设计模式之代理模式 代理人这个职业在中国有另外一个称呼,房产经济人、保险经济人,其实这个职业在国外都是叫做房产代理或者保险代理。顾名思义,就是由他们来帮我们处理这些对我们大部分...

硬核项目经理
2019/09/23
11
0
Redis的复制模式

Redis的复制功能分为同步(sync)和命令传播(command propagate)两个操作。 同步 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。 1. 旧版本的执行步骤 从服务器...

osc_s9cni3go
55分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部