1. 首页
2. 网络流
3. 本页

UVALive 7122 Tight Knight (最小割)

题意：~

思路：给定一个图，几个障碍点，问删除至多一条边能否使得起始位置到不了终点位置，即求最小割。数据范围较大，还卡SAP，ISAP，只能用dinic过？

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
#define pb push_back
#define Key_value ch[ch[root][1]][0]
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
const double eps = 1e-8;
const double pi = acos (-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int M = 1000100;
const int MAXN = 2000050;
const int MAXM = 18000000;

int dir[][2] = {1, 2, 2, 1, -1, 2, -2, 1, 1, -2, 2, -1, -1, -2, -2, -1};
struct Edge
{
    int to, next, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN];
void init()
{
    tol = 2;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw = 0)
{
    edge[tol] = (Edge){v, head[u], w, 0};
    head[u] = tol++;
    edge[tol] = (Edge){u, head[v], rw, 0};
    head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];
bool bfs(int s, int t, int n)
{
    int front = 0, tail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[tail++] = s;
    while(front < tail)
    {
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                if(v == t) return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}

int dinic(int s, int t, int n)
{
    int maxflow = 0;
    while(bfs(s, t, n))
    {
        for(int i = 0; i < n; ++i) cur[i] = head[i];
        int u = s, tail = 0;
        while(cur[s] != -1)
        {
            if(u == t)
            {
                int tp = INF;
                for(int i = tail - 1; i >= 0; i--)
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail - 1; i >= 0; i--)
                {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if(edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        tail = i;
                }
                u = edge[sta[tail] ^ 1].to;
            }
            else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
            {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                while(u != s && cur[u] == -1)
                    u = edge[sta[--tail] ^ 1].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

bool vis[1005][1005];
int main()
{
    int n, m, q;
    int sx, sy, ex, ey;
    while(~scanf("%d%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey, &q), n)
    {
        init();
        MS(vis, false);
        int x, y;
        for(int i = 0; i < q; ++i)
        {
            scanf("%d%d", &x, &y);
            vis[x][y] = 1;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                if(vis[i][j]) continue;
                int flow = 1;
                if((i == sx && j == sy) || (i == ex && j == ey)) flow = INF;
                int u = (i - 1) * m + j;
                addedge(u, u + n * m, flow);
                for(int k = 0; k < 8; ++k)
                {
                    int xx = i + dir[k][0];
                    int yy = j + dir[k][1];
                    if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
                    int v = (xx - 1) * m + yy;
                    addedge(u + n * m, v, 1);
                }
            }
        }
        int st = n * m * 2 + 1;
        int ed = n * m * 2 + 2;
        addedge(st, (sx - 1)*m + sy, INF);
        addedge((ex - 1)*m + ey, ed, INF);
        int ans = dinic(st, ed, n * m * 2 + 2);
        if(ans <= 1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

/*
1000 1000 1 1 1000 1000 0
*/