最大流，建图

题意：

图片说明

分析：

难点就在建图。
我们不难这样想：
将每一条边视作一个点，将每一个格子视作一个点。
格子点拆成两个。
然后这样建造：

但是，这很明显不能满足约束条件。
对于相邻的两个格点，如果他们相邻的边被选中时，两个格点的s-s1或者s2-ed都要减一，并且该边所代表的点再也不能走了！
很明显我们是做不到这个约束条件的！！！

我们再来仔细分析题目
1.对于每一个格点我们只能最多流其周遭尚未被占领的边数-1。
2.我们需要保证相邻的边，对两个格点都有约束作用，且边具有一次性的性质，及只能经过一次。
那么我们怎么办呢？
首先如何确定1
很简单，只要我们控制s-s1或者s2-ed的流量就可以了！
但是第二点呢？
结合上面的第一点的分析，我们可以这样做。
假设格点A于B相邻，那么我们连一条e(A,B,1)去掉A的s2,和B的s1
我们将边就视作边！！！
而如果想要同时约束两个格点的流量大小的话，那么只能将他们放在一条路径上。
即，如果我们想要通过相邻的这条边来获得流量的话，那么我们必须经过A的s1和B的s2，对两个格点都有所约束！！！

即我们染***r> 图片说明
我们按照奇偶染色，即一个是A一个是B。一个去掉s2,通过临边连入周围的格点，一个去掉s1。
如此我们就能实现，题目中所说的约束条件！！！
但是还有个细节：
如何处理边缘的格点呢？对于第一个格点如果它上面的边没有被画，我们怎么办呢？
很简单，如果该点是A类型,连e(A,ed,1)
如果是B类型，连e(s,B,1)

然后报个最大流，输出dinic(start,ed)+1就是正确答案了！

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int max_n = 20000;
const int max_m = 500000;
const int inf = 2e9;
int n, m;
struct edge{
    int to, cap, rev, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}

int iter[max_n];
int dist[max_n];
bool searchpath(int s,int t) {
    fill(dist, dist + t + 10, -1);
    queue<int> que;que.push(s);
    dist[s] = 0;
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap == 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}
int dinic(int start,int ed) {
    int flow = 0;int f;
    while (searchpath(start, ed)) {
        for (int i = 1;i <= ed;++i)iter[i] = head[i];
        while (f = matchpath(start, ed, inf))
            flow += f;
    }return flow;
}

int getpoint(int x,int y) {
    return (x - 1) * (n - 1) + y;
}
bool check(int x,int y) {
    return x > 0 && x <= n - 1 && y > 0 && y <= n - 1;
}
int dirx[4] = { 1,-1,0,0 };
int diry[4] = { 0,0,1,-1 };
char mp[200][200];
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1;i <= 2 * n - 1;++i)
        for (int j = 1;j <= 2 * n - 1;++j)
            cin >> mp[i][j];
    int start = (n - 1) * (n - 1) + 1;
    int ed = start + 1;
    for (int i = 1;i <= (n - 1);++i) {
        for (int j = 1;j <= (n - 1);++j) {
            int colour = ((i + j) & 1);
            int cuut = 0;
            int x = i * 2;int y = j * 2;
            for (int k = 0;k < 4;k++) {
                int xk = x + dirx[k];
                int yk = y + diry[k];
                if (mp[xk][yk] != '.')continue;
                ++cuut;
                if (colour == 0) {
                    if (check(i + dirx[k], j + diry[k]))
                        add(getpoint(i, j), getpoint(i + dirx[k], j + diry[k]), 1);
                    else add(getpoint(i, j), ed, 1);
                }
                else if (!check(i + dirx[k], j + diry[k]))
                    add(start, getpoint(i, j), 1);
            }if (colour == 0)
                add(start, getpoint(i, j), cuut - 1);
            else add(getpoint(i, j), ed, cuut - 1);
        }
    }cout << dinic(start, ed) + 1 << endl;
}

真的是有点难度的！！需要分析啊！！！多见见网络流的世面。

点阵

最大流，建图

题意：

分析：

代码如下：