「BZOJ 2673」「WF 2011」Chips Challenge

要求构造一个 $n \times n$ 的 $0/1$ 矩阵,满足下列限制的前提下 $1$ 的总数最多:

  • 对于某些位置,要求这些位置为 $1$。

  • 对于某些位置,要求这些位置必须为 $0$。

  • 第 $i$ 行与第$i$列中 $1$ 的个数相等。

  • 任意行列中$1$的个数不能超过总共 $1$ 个数的 $\frac{A}{B}$。

容易发现这是一道很流的题,我们考虑怎么流。

考虑怎么构图满足限制,发现网络流不好处理总流量和单边流量的限制关系,因为数据范围很小,所以我们把最后一条限制拿出来暴力枚举。

然后发现比较棘手的一个限制是每行每列的$1$的个数必须相等。我们考虑用费用流解决,因为费用流中满足最大流的优先级比满足最大费用的优先级高,和这道题中满足个数相等的限制的优先级比 $1$ 的个数多优先级更高是类似的。所以我们考虑对每行的点向每列的点连边,使其流量为无穷,费用为 $0$,这样构图一定会满足整个图满流,所以如果存在对应行列有价值的流量不相等的话,必定会导致流量不平衡,这样我们就解决掉了第三个限制。

然后考虑前两条限制,我们当然可以直接上下界莽,也可以采用一种比较套路的优化做法:我们令那些必须为 $1$ 的地方流量为 $MAX + 1$ ,其中 $MAX$为答案可能达到的最大值,因为要求最大费用,所以一定是满足必须的边跑完再跑其他边,最后的答案我们对 $MAX$ 取模即可,也非常好检查必须选的是否选了。

然后就做完了,这题给人一种很优美的感觉呢。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;
const int L = 10000;

int N, A, B, S, T, X[MAXN], Y[MAXN], cnt = 0, key = 0;
char s[55][55];

struct edge {
    int y, next, flow, v, rev;
}e[MAXN << 5];

int LINK[MAXN], len = 0, sum;

inline void ins(int x, int y, int flow, int v, int rev){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].flow = flow; e[len].v = v; e[len].rev = len + rev;
}

inline void Ins(int x, int y, int flow, int v){
    ins(x, y, flow, v, 1);
    ins(y, x, 0, -v, -1);
}

deque<int> q;
int dis[MAXN], fn[MAXN], fe[MAXN];
bool vis[MAXN];

bool SPFA(){
    up (i, 1, cnt) {
        dis[i] = -oo;
        vis[i] = 0;
    }
    dis[S] = 0; vis[S] = 1; q.push_back(S);
    while (!q.empty()) {
        int node = q.front(); q.pop_front();
        vis[node] = 0;
        Auto (i, node) if (e[i].flow && dis[e[i].y] < dis[node] + e[i].v) {
            dis[e[i].y] = dis[node] + e[i].v;
            fn[e[i].y] = node; fe[e[i].y] = i;
            if (!vis[e[i].y]) {
                vis[e[i].y] = 1;
                q.push_back(e[i].y);
            }
        }
    }
    return dis[T] != -oo;
}

int addflow(){
    int flow = oo;
    for (int node = T; node != S; node = fn[node]) {
        int i = fe[node];
        cmin(flow, e[i].flow);
    }
    for (int node = T; node != S; node = fn[node]) {
        int i = fe[node];
        e[i].flow -= flow;
        e[e[i].rev].flow += flow;
        sum += flow * e[i].v;
    }
}

int Work(int lim){
    up (i, 1, N) {
        Ins(S, X[i], lim, 0);
        Ins(Y[i], T, lim, 0);
        Ins(X[i], Y[i], oo, 0);
    }
    up (i, 1, N) up (j, 1, N) {
        if (s[i][j] == '.') Ins(X[i], Y[j], 1, 1);
        if (s[i][j] == 'C') Ins(X[i], Y[j], 1, L + 1);
    }
    sum = 0;
    while (SPFA()) addflow();
    up (i, 1, cnt) LINK[i] = 0;
    len = 0;
    if (sum / L != key) return -1;
    sum %= L;
    if (sum * A < B * lim) return -1;
    return sum;
}

int main(){
    int Case = 0;
    while (scanf("%d%d%d", &N, &A, &B) != EOF) {
        if (!N) break;
        cnt = 0;
        up (i, 1, N) scanf("%s", s[i] + 1); 
        key = 0;
        up (i, 1, N) up (j, 1, N) if (s[i][j] == 'C') key++;
        S = ++cnt; T = ++cnt;
        up (i, 1, N) X[i] = ++cnt, Y[i] = ++cnt;
        bool vaild = 0;
        down (i, N, 0) {
            int ans = Work(i);
            if (ans != -1) {
                printf("Case %d: %d\n", ++Case, ans - key);
                vaild = 1;
                break;
            }
        }
        if (!vaild) printf("Case %d: impossible\n", ++Case); 
    }
    return 0;
}