首页 > 其他分享 >POJ 3020 Antenna Placement

POJ 3020 Antenna Placement

时间:2023-08-02 14:16:04浏览次数:51  
标签:Placement idx Antenna ty int 城市 POJ include match

\(POJ\) \(3020\) \(Antenna\) \(Placement\)

一、题目描述

*--代表城市,o--代表空地

给城市安装无线网,一个无线网最多可以覆盖两座城市,问覆盖所有城市最少要用多少无线。

公式:最小路径覆盖 = 总节点数-最大匹配数

我们要尽可能多的建立能覆盖两个城市的基站(二分匹配最大匹配),剩下的城市每个城市建立一个基站。

二、\(Code\)

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <cstdio>

using namespace std;
const int N = 50, M = N * N;

char a[N][N]; // 原始矩阵

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dx[] = {-1, 0, 1, 0}; // 上右下左
int dy[] = {0, 1, 0, -1}; // 上右下左

int n, m; // n行m列

// 匈牙利算法
int st[M], match[M];
int dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (st[v]) continue;
        st[v] = 1;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ3020.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        // 初始化链式前向星
        memset(h, -1, sizeof h);
        idx = 0;

        scanf("%d %d", &n, &m); // n*m的矩阵

        for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1); // 使用char[],按行一次读入,快捷!

        int cnt = 0; // 城市个数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //*--代表城市,o--代表空地
                // 给城市安装无线网,一个无线网最多可以覆盖两座城市,问覆盖所有城市最少要用多少无线网。
                if (a[i][j] == '*') {
                    cnt++;
                    // 四周探测
                    for (int k = 0; k < 4; k++) {
                        int tx = i + dx[k], ty = j + dy[k];
                        if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
                        // 城市到城市建边,无向图,尽量让无线网构建在两个城市上,这样才能省资源,要不一个城市一个无向网太费了
                        if (a[tx][ty] == '*') add((i - 1) * m + j, (tx - 1) * m + ty);
                    }
                }
            }
        }

        // 匈牙利
        memset(match, -1, sizeof match);
        int res = 0;
        for (int i = 1; i <= n * m; i++) {
            memset(st, 0, sizeof st);
            if (dfs(i)) res++;
        }
        // 无向图,重复计算,然后除以2,就是最大匹配数
        printf("%d\n", cnt - res / 2);
    }
    return 0;
}

标签:Placement,idx,Antenna,ty,int,城市,POJ,include,match
From: https://www.cnblogs.com/littlehb/p/17600501.html

相关文章

  • H - Collecting Bugs POJ-2096
    H-CollectingBugsPOJ-2096期望dp题意根据题意可以将原题意转换成:有个\(n*s\)的矩阵,每次会随机选取一个格子填上颜色,问每行每列都填上颜色的期望次数。思路dp,显然是期望dp,那么设\(dp_{i,j}\)为已经有\(i\)行\(j\)列填上颜色,到目标还需的次数的期望,那么每次......
  • POJ - Buy Tickets
    Smiling&Weeping----你看这个人,嘴里说着喜欢我却又让我这么难过DescriptionRailwayticketsweredifficulttobuyaroundtheLunarNewYearinChina,sowemustgetupearly......
  • POJ 1548 Robots
    \(POJ\)\(1548\)\(Robots\)题意相当于给出\(N\)个坐标点,因为机器人只能向下或者向右走,所以如果能到达其他点,则连接这两个点,即line[i][j]=1最小路径覆盖数:对于一个\(DAG\)(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长度可以为零;(有向图中找一些路径,使......
  • element-ui 日期选择器报错 Prop being mutated: "placement"
    报错信息解决方法,添加placement="bottom-start"<el-date-pickerv-model="queryParams.startTime"type="date"placeholder="开始时间"value-format="yyyy-MM-ddHH:mm:ss"placement="bottom-start">......
  • POJ1904 King's Quest
    \(POJ1904\)\(King's\)\(Quest\)一、题目描述有\(n\)个王子,每个王子都有\(k\)个喜欢的妹子,每个王子只能和喜欢的妹子结婚。现有一个匹配表,将每个王子都与一个自己喜欢的妹子配对。请你根据这个表得出每个王子可以和几个自己喜欢的妹子结婚,按序号升序输出妹子的编号,这个表应满......
  • poj 2886 Who Gets the Most Candies? (线段树单点更新应用)
                           poj2886WhoGetstheMostCandies?DescriptionNchildrenaresittinginacircletoplayagame.Thechildrenarenumberedfrom1toNinclockwiseorder.Eachofthemhasacardwithanon-zerointegeronit......
  • POJ 3694 Network
    POJ3694Network一、题目大意\(n\)个点,\(m\)个边,连通图。点与点之间通过边连接,如果切断某个边使得有点与其他点连接断开(连通分支增加),则称这种边为桥梁(离散上叫割边)。接下来有\(Q\)个操作,每操作一次,也就是切断某条边后,输出当前存在的桥梁数量。二、样例分析我们看这个4......
  • (Relax 数论1.26)POJ 1496 Word Index(计算一个字符串在字典中的位置)
    大致题意:(与POJ1850基本一致)输出某个str字符串在字典中的位置,由于字典是从a=1开始的,因此str的位置值就是在str前面所有字符串的个数+1规定输入的字符串必须是升序排列。不降序列是非法字符串要求用循环输入,输入若干组字符串,若输入非法字符串则输出0,但不结束程序,这是和POJ1850......
  • POJ 1458 Common Subsequence(动态规划)
    传送门代码如下:#include<iostream>#include<cstdio>usingnamespacestd;intmaxLen[1000][1000];intmain(){strings1,s2;while(cin>>s1>>s2){intlength1=s1.length();intlength2=s2.length();......
  • 题解 POJ3318【Matrix Multiplication】
    postedon2022-10-2119:56:08|under题解|sourceproblem判断三个\(n\timesn\)的矩阵是否满足\(A\timesB=C\),\(n\leq500\)。solution随机一个行向量\(v\)。若\(a\timesb=c\),则有\(v\timesa\timesb=v\timesc\)(不充分)。显然相乘复杂度仅为\(O(n^2)\)。类似于......