POJ 3020 Antenna Placement 二分比對

二分圖比對問題。

一開始想不到怎麼建圖，參考了别人的代碼之後才寫出來  = - = 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 1005
#define inf 1<<28
using namespace std;

char a;
bool visit[Max];
int Map[Max][Max],match[Max];
int Map1[Max][Max];
int move[4][2]= {{0,1},{1,0},{-1,0},(0,-1)};//四個方向
int n,m;
int v1,v2;//兩邊點集數


//找增廣軌
int dfs(int cur)
{
    int i;
    for(i=1; i<=v2; i++)
    {
        if(!visit[i]&&Map1[cur][i])
        {
            visit[i]=1;
            if(match[i]==0||dfs(match[i]))
            {
                match[i]=cur;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    //freopen("in1.txt","w",stdout);
    int i,j,k,l;
    int T;
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
            cin>>n>>m;
            int num=0;
            memset(Map,0,sizeof(Map));
            memset(Map1,0,sizeof(Map1));
            memset(match,0,sizeof(match));
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=m; j++)
                {
                    cin>>a;
                    if(a=='*')
                    {
                        Map[i][j]=++num;//将每個需要覆寫的城市标号1-num;
                    }
                }
            }
//建圖
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=m; j++)
                {
                    if(Map[i][j])
                    {
                        for(k=0; k<4; k++)
                        {
                            int x=i+move[k][0];
                            int y=j+move[k][1];
                            if(Map[x][y])
                            {
                                Map1[Map[x][y]][Map[i][j]]=Map1[Map[i][j]][Map[x][y]]=1;//如果兩個城市可以到達，則加入集合，無向圖，是以兩邊都要加
                            }

                        }
                    }
                }
            }
            v1=v2=num;


            int sum=0;
            for(i=1; i<=v1; i++)
            {
                memset(visit,0,sizeof(visit));
                sum+=dfs(i);//找最大比對
            }
            cout<<num-sum/2<<endl;//無向二分圖：最小路徑覆寫數=點的總數-最大比對/2，這個我也不懂。。看大神是這麼說的。。
        }
    }
    return 0;
}
           

總的來說，不能講問題轉化掉.

這題建圖的想法很好，值得借鑒。