hdu 5093 放置戰艦 二分圖匹配

hdu 5093 放置戰艦 二分圖匹配

給定一個MxN大小的圖，有3種點，冰山、浮冰、海。現在希望能在圖中放置盡可能多的船。船的四個方向上不能有其他的船，除非有冰山阻隔。

最自然的想到搜索，但是由於矩陣大小有50^2，顯然會超時

其實可以將一行被冰山隔開且包含海水的連續區域叫做“塊”。
把每個橫向“塊”看做二部圖中的X中的頂點，豎向“塊”看做集合中Y的頂點，若兩個“塊”有公共的頂點海水，於是就連一條邊。這樣就轉換成了沒有公共頂點的最大邊集，即最大匹配。
我們怎麼去求“塊”呢？用一個2個二維數組xs,ys來對水平方向和垂直方向上的“塊”進行編號，編號之後如果兩個塊有公共的海水的話，那麼就在“塊”與“塊”之間連邊，等於說是，這個點只能利用一次。

#include 
#include 
#include 
#include 
#define RD(x) scanf(%d,&x)
#define RD2(x,y) scanf(%d%d,&x,&y)
#define RD3(x,y,z) scanf(%d%d%d,&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
using namespace std;

const int MAXN = 55;
const int MAXM = 1005;

struct Edge
{
    int v, next;
}edge[MAXM];

char map[MAXN][MAXN];
int first[MAXM], link1[MAXM];
bool vis[MAXM];

int n, m;
int cnt;
int xn;

int xs[MAXN][MAXN], ys[MAXN][MAXN];

void init()
{
    cnt = 0;
    clr1(first),clr1(link1);
    clr0(xs),clr0(ys);
}

void read_graph(int u, int v)
{
    edge[cnt].v = v;
    edge[cnt].next = first[u], first[u] = cnt++;
}

bool dfs(int u)
{
    for(int e = first[u]; e != -1; e = edge[e].next)
    {
        int v = edge[e].v;
        if(!vis[v])
        {
            vis[v] = 1;
            if(link1[v] == -1 || dfs(link1[v]))
            {
                link1[v] = u;
                return true;
            }
        }
    }
    return false;
}

void read_graph2()
{
    RD2(n,m);
    for(int i = 0; i < n; i++) scanf(%s, map[i]);
    int tot = 0;
    for(int i = 0; i < n; i++)
    {
        int flag = 0;
        for(int j = 0; j < m; j++)
        {
            if(map[i][j] == '*')
            {
                if(flag == 0) tot++;
                xs[i][j] = tot; flag = 1;
            }
            else if(map[i][j] == '#') flag = 0;
        }
    }
    xn = tot;
    tot = 0;
    for(int j = 0; j < m; j++)
    {
        int flag = 0;
        for(int i = 0; i < n; i++)
        {
            if(map[i][j] == '*')
            {
                if(flag == 0) tot++;
                ys[i][j] = tot; flag = 1;
            }
            else if(map[i][j] == '#') flag = 0;
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            int u = xs[i][j], v = ys[i][j];
            if(u && v)
            {
                read_graph(u, v);
            }
        }
    }
}

void solve()
{
    int ans = 0;
    for(int i = 1; i <= xn; i++)
    {
        clr0(vis);
        if(dfs(i)) ans++;
    }
    printf(%d
, ans);
}

int main()
{
    int _;RD(_);
    while(_--)
    {
        init();
        read_graph2();
        solve();
    }
    return 0;
}