POJ 3020 Antenna Placement(二分圖建圖訓練 + 最小路徑覆蓋)

POJ 3020 Antenna Placement(二分圖建圖訓練 + 最小路徑覆蓋)

 

 

 

 

Antenna Placement Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6692   Accepted: 3325

 

Description

The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.

 

 

題意：給定一個地圖，*代表城市，o代表空地，用天線來覆蓋相鄰的兩個城市，問最少需要多少天線？（所謂相鄰是指上下左右4個方向相鄰）

 

題意很清晰，求二分圖的最小路徑覆蓋，難點還是建圖。。。今天運氣好，建圖的思路來源於ZOJ1654

PS，覆蓋的是城市，不是空地，開始我就數錯了

 

思路：剛好今天做了ZOJ 1654，和1654差不多，那個采用分塊的思想，而這個是把單個的城市當做一塊，進行編號從而構建圖的連通性，至於最後的輸出結果，城市總數減去最大匹配數==剩余的城市數，也就是最大獨立集合數，剩余城市的個數說明他們無法進行增廣/匹配，那麼就需要單獨建設天線，而 匹配數/2 == 一個天線覆蓋兩個城市

所以最終answer = city - ans + ans/2

 

ZOJ 1654 AC代碼

 

 

Accepted 1584K 16MS C++

 

想明白後，直接開敲，手殘一次，1A

 

 

#include 
#include 
#include 
#include 
#include 
#include 
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 60;
const int maxm = 600;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
int ma[maxn][maxn];
char MAP[maxn][maxn];
int G[maxm][maxm];
int line[maxm];
bool vis[maxm];
int mv[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,city;
int DFS(int u)
{
    for(int v = 1;v<=city;v++)
    {
        if(G[u][v]==1 && !vis[v])
        {
            vis[v] = 1;
            if(line[v]==-1 || DFS(line[v]))
            {
                line[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int K_M()
{
    int ans = 0;
    memset(line,-1,sizeof(line));
    for(int i = 1;i<=city;i++)
    {
        init(vis);
        ans += DFS(i);
    }
    return ans;
}
void Get_G(int i,int j)//構圖
{
    for(int dir = 0;dir<4;dir++)
    {
        int wx = i + mv[dir][0];
        int wy = j + mv[dir][1];
        if(MAP[wx][wy]=='*')
        {
            G[ma[i][j]][ma[wx][wy]] = 1;//構建當前城市與它4個方向相鄰的城市連通
        }
    }
}
int main()
{
    int t;
    scanf(%d,&t);
    char a[500];
    while(t--)
    {
        scanf(%d%d,&n,&m);
        city = 0;

        gets(a);//不加，測試數據就讀不進。。。。。我特別無語

        init(ma); init(G);
        for(int i = 0;i