算法——最大流

最大流

• 洛谷P1418——构造矩阵
• • 1、建图
  • 2、解题步骤
• 洛谷P6054——开门大吉
• • 建图毒瘤

洛谷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 
#include 
#include 
#include 
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——开门大吉

建图毒瘤

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

代码不附了，省点地方。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！