首页 > 代码库 > HDU 4888 Redraw Beautiful Drawings（2014 Multi-University Training Contest 3）
HDU 4888 Redraw Beautiful Drawings（2014 Multi-University Training Contest 3）
题意：给定n*m个格子，每个格子能填0-k 的整数。然后给出每列之和和每行之和，问有没有解，有的话是不是唯一解，是唯一解输出方案。
思路：网络流，一共 n+m+2个点 源点 到行连流量为 所给的 当前行之和。 每行 连到每一列 一条流量为 k的边，每列到汇点连 列和。如果流量等于总和则有解，反之无解（如果列总和不等于行总和也无解）。 判断方案是否唯一 找残留网络是否存在长度大于2的环即可，有环说明不唯一。
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include <iostream>#include<climits>using namespace std;const int N = 1000;const int M = 1000000;int n;int ecnt, head[N], nx[M], to[M], va[M], cur_edge[N];int source, target, flow, pre[N], lev[N], qu[N], sign;void addedge(int u, int v, int w) { to[ecnt] = v; nx[ecnt] = head[u]; va[ecnt] = w; head[u] = ecnt++;}bool bfs(int s, int t) { std::fill(lev, lev + n, -1); sign = t; lev[t] = 0; int st = 0, ed = 0; qu[ed++] = t; while (st != ed && lev[s] == -1) { int u = qu[st++]; for (int i = head[u]; i != -1; i = nx[i]) { if (va[i ^ 1] > 0 && lev[to[i]] == -1) { lev[to[i]] = lev[u] + 1; qu[ed++] = to[i]; } } } return lev[s] != -1;}void push() { int delta = INT_MAX, u, p; for (u = target; u != source; u = to[p ^ 1]) { p = pre[u]; delta = std::min(delta, va[p]); } for (u = target; u != source; u = to[p ^ 1]) { p = pre[u]; va[p] -= delta; if (!va[p]) {//注意double时要改 sign = to[p ^ 1]; } va[p ^ 1] += delta; } flow += delta;}void dfs(int u) { if (u == target) push(); else { for (int i = cur_edge[u]; i != -1; i = nx[i]) { if (va[i] > 0 && lev[u] == lev[to[i]] + 1) { pre[to[i]] = i; dfs(to[i]); if (lev[sign] > lev[u]) { return; } sign = target; } } lev[u] = -1; }}void dinic(int s, int t, int node_cnt) { source = s; target = t; n = node_cnt; //construct graph flow = 0; while (bfs(source, target)) { for (int i = 0; i < n; ++i) { cur_edge[i] = head[i]; } dfs(source); }}int nc, kc, mc, sum1, sum2;int r[410], c[410];void init() { sum1 = sum2 = 0; for (int i = 0; i < nc; ++i) { scanf("%d", &r[i]); sum1 += r[i]; } for (int i = 0; i < mc; ++i) { scanf("%d", &c[i]); sum2 += c[i]; }}int flag = 0;bool bo[1000];bool bb[1000];int cas[350000];int ri = 0;void gao(int now, int fa) {//找环 if(flag)return; //printf("->%d ",now); bo[now] = true; for (int i = head[now]; i != -1; i = nx[i]) { int u = to[i]; if (u == fa) continue; if (va[i] == 0) continue; // printf(" {%d %d}\n",now,u); if (bb[u]) { // puts("fuck"); flag = 1; return; } if (cas[i] == ri) continue; cas[i] = ri; //if(bo[u])continue; bb[u] = true; gao(u, now); bb[u] = false; }}void solve() { if (sum1 != sum2) { puts("Impossible"); return; } std::fill(head, head + mc + nc + 5, -1); ecnt = 0; int s, t; s = nc + mc; t = s + 1; // printf("st:%d %d\n",s,t); for (int i = 0; i < nc; ++i) { for (int j = 0; j < mc; ++j) { // printf("[%d %d]\n",i,j+nc); addedge(i, j + nc, kc); addedge(j + nc, i, 0); } } for (int i = 0; i < nc; ++i) { // printf("[%d %d]\n",s,i); addedge(s, i, r[i]); addedge(i, s, 0); } for (int i = 0; i < mc; ++i) { // printf("[%d %d]\n",i+nc,t); addedge(i + nc, t, c[i]); addedge(t, i + nc, 0); } dinic(s, t, t + 2); // printf("flow:%d\n",flow); if (flow == sum1) { memset(bo, 0, sizeof(bo)); memset(bb, 0, sizeof(bb)); flag = 0; for (int i = 0; i <= t; ++i) { if(flag)break; bb[i] = true; gao(i, -1); bb[i] = false; } if (flag) puts("Not Unique"); else { puts("Unique"); for (int i = 0; i < nc; ++i) { for (int j = 0; j < mc; ++j) { int now = i * mc + j; printf("%d", va[now << 1 | 1]); if (j == mc - 1) puts(""); else printf(" "); } } } } else puts("Impossible");}int main() { memset(cas, 0, sizeof(cas)); while (scanf("%d%d%d", &nc, &mc, &kc) != EOF) { ++ri; init(); solve(); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。