[数据结构与算法]CodeForces 1517G Starry Night Camping（网络流最小割）

CodeForces 1517G Starry Night Camping

problem

洛谷链接

solution

这个平行四边形的脑洞我?真的长见识了

本题最离谱的要求就是：平行四边形的一条边平行于 $x$ 轴。

而往往这种离谱要求就是正解的途径。(((φ(◎ロ◎;)φ)))

首先不观察也能知道，中心点的上下必须选一个，左右必须选一个，这样就确定了三个点。

最后一个点在上下和左右选出来后也就有了选择限制。

这个选择限制就是不能让选的左右点与中心点的边成为对角线（这种斜着的平行四边形是被允许存在的）。

再看，还要求中心点的坐标都是偶数，我们用 O 表示奇数，E 表示偶数。

那么中心点就是 (E,E)，左右点都是 (E,O)，上下点都是 (O,E)，剩下的一个点都是 (O,O)。

换言之，平行四边形的四个顶点一定是由上面四类各出一个点构成的。

我们用路径来刻画平行四边形的边。

发现不合法的平行四边形都可以被表示为 $(O,O)\to (O,E)\to (E,E)\to (E,O)$，一条边连接的两个点的距离恰好为 $1$。

这说明，如果将点按横纵坐标分成四大类，最后是不能出现长度为 $4$ 的链的。

而这四类之间的边是唯一的，定向的。

可以用拆点+网络流。把一个坐标点拆成入点和出点，再建一个超级源点和超级汇点。

入点和出点之间就是坐标点的删除代价，其余边容量无穷即可。

最后是不能让 $S?T$ 之间存在流量的，也就是要把 $S/T$ 割开，即最小割问题。

code

#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define int long long
#define maxn 2005
queue < int > q;
int s, t, cnt = -1;
int dep[maxn], head[maxn], cur[maxn];
struct node { int to, nxt, flow; }E[maxn << 4];

void addedge( int u, int v, int w ) {
    E[++ cnt] = { v, head[u], w };
    head[u] = cnt;
    E[++ cnt] = { u, head[v], 0 };
    head[v] = cnt;
}

bool bfs() {
    memset( dep, 0, sizeof( dep ) );
    memcpy( cur, head, sizeof( head ) );
    q.push( s ), dep[s] = 1;
    while( ! q.empty() ) {
        int u = q.front(); q.pop();
        for( int i = head[u];~ i;i = E[i].nxt ) {
            int v = E[i].to;
            if( ! dep[v] and E[i].flow > 0 ) {
                dep[v] = dep[u] + 1;
                q.push( v );
            }
        }
    }
    return dep[t];
}

int dfs( int u, int cap ) {
    if( ! cap or u == t ) return cap;
    int flow = 0;
    for( int i = cur[u];~ i;i = E[i].nxt ) {
        cur[u] = i; int v = E[i].to;
        if( dep[v] == dep[u] + 1 and E[i].flow > 0 ) {
            int w = dfs( v, min( cap, E[i].flow ) );
            E[i ^ 1].flow += w;
            E[i].flow -= w;
            flow += w;
            cap -= w;
            if( ! cap ) break;
        }
    }
    return flow;
}

int dinic() {
    int ans = 0;
    while( bfs() ) ans += dfs( s, inf );
    return ans;
}

int n;
int x[maxn], y[maxn], w[maxn], type[maxn];

signed main() {
    memset( head, -1, sizeof( head ) );
    scanf( "%lld", &n );
    int ans = 0;
    s = 1, t = n + 1 << 1;
    for( int i = 1;i <= n;i ++ ) {
        scanf( "%lld %lld %lld", &x[i], &y[i], &w[i] );
        if( (x[i] & 1) and (y[i] & 1) ) type[i] = 1;
        if( (x[i] & 1) and !(y[i] & 1) ) type[i] = 2;
        if( !(x[i] & 1) and !(y[i] & 1) ) type[i] = 3;
        if( !(x[i] & 1) and (y[i] & 1) ) type[i] = 4;
        ans += w[i];
    }
    for( int i = 1;i <= n;i ++ ) addedge( i << 1, i << 1 | 1, w[i] );
    for( int i = 1;i <= n;i ++ ) if( type[i] == 1 ) addedge( s, i << 1, inf );
    for( int k = 1;k <= 3;k ++ )
        for( int i = 1;i <= n;i ++ )
            if( type[i] == k )
                for( int j = 1;j <= n;j ++ )
                    if( type[j] == k + 1 )
                        if( fabs( x[i] - x[j] ) + fabs( y[i] - y[j] ) == 1 )
                            addedge( i << 1 | 1, j << 1, inf );
    for( int i = 1;i <= n;i ++ ) if( type[i] == 4 ) addedge( i << 1 | 1, t, inf );
    printf( "%lld\n", ans - dinic() );
    return 0;
}