HDU – 3338 Kakuro Extension(最大流)
分类：ACM-图论ACM-图论-网络流
题目大意：看一下图基本就知道了
解题思路：难点是构图。。 设置一个超级源点和所有的行的和相连，容量为该行的和 – 该行和由几个数相加得到 设置一个超级汇点，和所有列的和相连，容量为该列的和 – 该列和由几个数相加得到 接着就是空白部分和 “行和“和 “列和“的关系了 空白连向该行的行和，权值为8 空白连向该列的列和，权值也为8 为什么为8，而不是9，因为流量也可能为0，但是0是不能填的，所以将容量设为8，最后取值的时候加1即可
;Edge {int from, to, cap, flow;Edge() {}Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {}};struct ISAP {int p[N], num[N], cur[N], d[N];int t, s, n, m;bool vis[N];vector<int> G[N];vector<Edge> edges;void init(int n) {this->n = n;for (int i = 0; i <= n; i++) {G[i].clear();d[i] = INF;}edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);}bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;d[t] = 0;vis[t] = 1;Q.push(t);while (!Q.empty()) {int u = Q.front();Q.pop();for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i] ^ 1];if (!vis[e.from] && e.cap > e.flow) {vis[e.from] = true;d[e.from] = d[u] + 1;Q.push(e.from);}}}return vis[s];}int Augment() {int u = t, flow = INF;while (u != s) {Edge &e = edges[p[u]];flow = min(flow, e.cap – e.flow);u = edges[p[u]].from;}u = t;while (u != s) {edges[p[u]].flow += flow;edges[p[u] ^ 1].flow -= flow;u = edges[p[u]].from;}return flow;}int Maxflow(int s, int t) {this->s = s; this->t = t;int flow = 0;BFS();if (d[s] > n)return 0;memset(num, 0, sizeof(num));memset(cur, 0, sizeof(cur));for (int i = 0; i < n; i++)if (d[i] < INF)num[d[i]]++;int u = s;while (d[s] <= n) {if (u == t) {flow += Augment();u = s;}bool ok = false;for (int i = cur[u]; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow && d[u] == d[e.to] + 1) {ok = true;p[e.to] = G[u][i];cur[u] = i;u = e.to;break;}}if (!ok) {int Min = n;for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow)Min = min(Min, d[e.to]);}if (–num[d[u]] == 0)break;num[d[u] = Min + 1]++;cur[u] = 0;if (u != s)u = edges[p[u]].from;}}return flow;}};ISAP isap;#define M 110struct Node {int row, col, val;Node() {}Node(int row, int col, int val): row(row), col(col), val(val){}}row[N], col[N];int n, m;int empty[M][M];char map[M];void solve() {int cnt_row = 0, cnt_col = 0, cnt_empty = 0;memset(empty, 0, sizeof(empty));for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {scanf(“%s”, map);if (strcmp(map, “…….”) == 0)empty[i][j] = ++cnt_empty;else if(map[3] == ‘\\’) {int t;if (map[0] != ‘X’) {t = (map[0] – ‘0’) * 100 + (map[1] – ‘0’) * 10 + (map[2] – ‘0’);col[++cnt_col] = Node(i, j, t);}if (map[4] != ‘X’) {t = (map[4] – ‘0’) * 100 + (map[5] – ‘0’) * 10 + (map[6] – ‘0’);row[++cnt_row] = Node(i, j, t);}}}int s = 0, t = cnt_empty + cnt_row + cnt_col + 1;isap.init(t);for (int i = 1; i <= cnt_row; i++) {int x = row[i].row;int cnt = 0;for (int y = row[i].col + 1; y <= m; y++) {if(empty[x][y]) {cnt++;isap.AddEdge(i, cnt_row + empty[x][y], 8);}elsebreak;}isap.AddEdge(s, i, row[i].val – cnt);}for (int i = 1; i <= cnt_col; i++) {int y = col[i].col;int cnt = 0;for (int x = col[i].row + 1; x <= n; x++) {if (empty[x][y]) {cnt++;isap.AddEdge(cnt_row + empty[x][y], cnt_row + cnt_empty + i, 8);}elsebreak;}isap.AddEdge(cnt_row + cnt_empty + i, t, col[i].val – cnt);}isap.Maxflow(s, t);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (empty[i][j]) {int ans = 0;for (int k = 0; k < isap.G[empty[i][j] + cnt_row].size(); k++) {Edge &e = isap.edges[isap.G[empty[i][j] + cnt_row][k]];if (e.to > cnt_row + cnt_empty) {ans += e.flow;break;}}printf(“%d “, ans + 1);}elseprintf(“_ “);}printf(“\n”);}}int main() {while (scanf(“%d%d”, &n, &m) != EOF) {solve();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇HDU – 3081 Marriage Match II(二分图最大匹配 ＋ 并查集)
顶0踩0
，有山就有路，有河就能渡。
