洛谷P1418——构造矩阵

洛谷P1418
使用最大流搜索出是否有解。

1、建图

首先，需要图化二维矩阵，将二维矩阵的所有行和列，转化成图的结点，即每行都向每列连一条权值为1的边，表示该位置的元素最多填1，之后从源点向每行连一个权值为本行总和的边，最后从每列到汇点连一条权值为本列总和的边。

2、解题步骤

1. 先跑一遍 dinic，获得一个可行解，并将可行解用数组存储起来；
2. 遍历可行解数组，如果数组在 w[i,j] 填 0，则删除该边及其反向边（因为后续的解该边不会再被用到了，即已经最优），如果是 1，则将 S->i，j->T 容量+1，看是否还有可行解，如果有，证明 a[i,j] 可以从1变成0。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e9+7;
const int N = 210, M = 5e4+7;
int h[N], e[M], f[M], ne[M], cur[N], d[N], r[N], c[N], q[N], cnt = 0;
int w[210][210], a[210][210], id[210][210];
int n, m, S, T;

void init() {
    cnt = 0; 
    memset(h, -1, sizeof h);
}

void add(int u, int v, int c) {
    id[u][v] = cnt, w[u][v] = c;
    e[cnt] = v, f[cnt] = c, ne[cnt] = h[u], h[u] = cnt++;
    id[v][u] = cnt, w[v][u] = 0;
    e[cnt] = u, f[cnt] = 0, ne[cnt] = h[v], h[v] = cnt++;
}

void change(int i, int j, int val) {
    f[id[S][i]] += val;
    w[S][i] += val; 
    f[id[j+n][T]] += val; 
    w[j+n][T] += val;
}

bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[tt++] = S, d[S] = 0, cur[S] = h[S];
    while (hh < tt) {
        int u = q[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int vv = e[i];
            if (d[vv] == -1 && f[i]) {
                cur[vv] = h[vv];
                d[vv] = d[u] + 1; 
                q[tt++] = vv;
                if (vv == T) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int vv = e[i];
        if (d[vv] == d[u] + 1 && f[i]) {
            int t = dfs(vv, min(limit - flow, f[i]));
            if (!t) d[vv] = -1;
            flow += t, f[i] -= t, f[i^1] += t;
            w[u][vv] = f[i], w[vv][u] = f[i^1];
        }
    }
    return flow;
}

void show() {
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            if (e[j] != S && !f[j])
                printf("(%d,%d) ", i, e[j]-n);
        }
        printf("\n");
    }
}

int dinic() {
    int flow = 0, r = 0; 
    while (bfs()) while(r = dfs(S,  INF)) flow += r;
    return flow;
}

int main() {
    init();
    scanf("%d%d", &n, &m);
    S = n+m+1, T = n+m+2;
    int sum = 0, maxflow = 0;
    for (int i = 1; i <= n; i++) 
        scanf("%d", &r[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) 
        sum += c[i];
    for (int i = 1; i <= n; i++)
        add(S, i, r[i]);
    for (int i = 1; i <= m; i++) 
        add(i+n, T, c[i]);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            add(i, j+n, 1);
    
    maxflow = dinic();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!w[i][j+n]) {
                maxflow--;
                change(i, j, 1);
            }
            else 
                w[i][j+n] = f[id[i][j+n]] = f[id[i][j+n]^1] = 0;
            maxflow += dinic();
            if (maxflow >= sum) a[i][j] = 0;
            else {
                a[i][j] = 1;
                maxflow++;
                change(i, j, -1);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) 
            printf("%d", a[i][j]);
        printf("\n");
    }

    return 0;
}

洛谷P6054——开门大吉

建图毒瘤

最小割==最大流
建图不懂的话，请看这张图，应该就懂了。

代码不附了，省点地方。