题目：

Battle ships

2
4 4
*ooo
o###
**#*
ooo*
4 4
#***
*#**
**#*
ooo#

3
5

题意：

          给你一个图，"*"代表海，"#"代表冰山，"o"代表浮冰。问你最多能停多少艘军舰在海上。但是有条件：任意两艘军舰不能在同一行或同一列，在同一列的唯一条件是中间有冰山隔开，浮冰不起隔作用，浮冰上面不停船。

思路：

         二分匹配中的行列匹配，但是要变形，所谓的变形在于拆点，先是给行编号，遇到冰山就拆点。接着是行编号，也是遇到冰山就拆点。

         然后再进行二分匹配，就可以达到目标。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#include<cmath>
#define PI 2*asin(1.0)
#define LL __int64
const int  MOD = 1e9 + 7;
const int N = 3e3 + 15;
const int INF = (1 << 30) - 1;
const int letter = 130;
using namespace std;
int tc;
int n, m;
int s , t;
short vis1[N][N], vis2[N][N];
char dis[N][N];
int vis[N];
int x[N], y[N];
int cur[N];
struct node {
    int from, to, cap, flow;
};
vector<node>edges;
vector<int>G[N];
void init() {
    for(int i = 0; i < N - 10; i++)
        G[i].clear();
    edges.clear();
}
void addedge(int from, int to, int cap) {
    edges.push_back((node) {
        from, to, cap, 0
    });
    edges.push_back((node) {
        to, from, 0, 0
    });
    int v = edges.size();
    G[from].push_back(v - 2);
    G[to].push_back(v - 1);
}
bool bfs() {
    memset(vis, -1, sizeof(vis));
    queue<int>q;
    while(!q.empty()) q.pop();
    vis[s] = 0;
    q.push(s);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int i = 0; i < G[x].size(); i++) {
            node &e = edges[G[x][i]];
            if(vis[e.to] < 0 && e.cap > e.flow) {
                vis[e.to] = vis[x] + 1;
                if(e.to == t) return 1;
                q.push(e.to);
            }
        }
    }
    return 0;
}
int dfs(int x, int a) {
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int &i = cur[x]; i < G[x].size(); i++) {
        node &e = edges[G[x][i]];
        if(vis[x] + 1 == vis[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {

            e.flow += f;
            flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}
int maxflow(int s, int t) {
    int flow = 0;
    while(bfs()) {
        memset(cur, 0, sizeof(cur));
        flow += dfs(s, INF);
    }
    return flow;
}
int main() {
    cin >> tc;
    while(tc--) {
        init();
        s = 0;
        int num = 1;
        scanf("%d%d", &n, &m);
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(vis1, 0, sizeof(vis1));
        memset(vis2, 0, sizeof(vis2));
        getchar();
        for(int i = 0; i < n; i++) {
            for(int j  = 0; j < m; j++) {
                scanf("%c", &dis[i][j]);
            }
            getchar();
        }
        /// hang
        for(int i = 0; i < n; i++) {
            int flag = 1, q = 0;
            for(int j = 0; j < m; j++) {
                if(dis[i][j] == '*') vis1[i][j] = num, flag = 0, q = 1, x[num] = 1;
                if(dis[i][j] == '#' && flag == 0) num++, flag = 1;
            }
            if(q == 1 && i != n - 1)num++;
        }
        num++;
        for(int j = 0; j < m; j++) {
            int flag = 1, q = 0;
            for(int i = 0; i < n; i++) {
                if(dis[i][j] == '*') vis2[i][j] = num, flag = 0, q = 1, y[num] = 1;
                if(dis[i][j] == '#' && flag == 0) num++, flag = 1;
            }
            if(q == 1) num++;
        }
        t = n + m + 15;
        for(int i = 0; i < N; i++)
            if(x[i]) addedge(s, i, 1);
        for(int i = 0; i < N; i++)
            if(y[i]) addedge(i, t, 1);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(dis[i][j] == '*') addedge(vis1[i][j],vis2[i][j],1);
            }
        }
        printf("%d\n",maxflow(s,t));
    }
    return 0;
}

HDU 5093Battle ships(2014上海邀请赛)

原文：http://blog.csdn.net/u014325920/article/details/42975523