首页 > 代码库 > HDU 4888 Redraw Beautiful Drawings (2014-多校3-1002，最大流，判最大流有多解)
HDU 4888 Redraw Beautiful Drawings (2014-多校3-1002，最大流，判最大流有多解)
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=4888
题意：
给一个n*m的矩阵的n行之和和m列之和以及限制k，使用0-k的数字填充矩阵使得其行与列之和为给定值
如果不行则输出Impossible
如果有多解则输出Not Unique
如果有一解则输出Unique，并输出构造的矩阵
方法：
最大流，判最大流有多解
1、建图：
每一行一个点，每一列一个点
源点与第i个行点连边，权值为第i行之和
第j个列点与汇点连边，权值为第j行之和
第i个行点与第j个列点连边，权值为k
2、跑最大流
3、如果源点与n个行点都流满且m个列点与汇点都流满，则有解，否则无解
4、判最大流有多解：
如果有多解，则某两点流量可以为(f1,f2)，(f1-f,f2+f)，所以可以根据这个结论判最大流是否有多解：
在残余网络中，如果存在大小大于2的环，则可以出现上述情况，即：有多解
1 bool dfsc(int u, int fa) 2 { 3 vis[u] = 1; 4 for (int i = head[u]; ~i; i = edge[i].next) 5 { 6 int v = edge[i].v; 7 if (v == fa || edge[i].flow == edge[i].cap) continue; 8 if (vis[v] || dfsc(v, u)) return 1; 9 }10 vis[u] = 0;11 return 0;12 }13 bool check()14 {15 memset(vis, 0, sizeof(vis));16 for (int i = 2; i < N + 2; i++)17 {18 if (!vis[i])19 {20 vis[i] = 1;21 if (dfsc(i, i)) return 0;22 vis[i] = 0;23 }24 }25 return 1;26 }
5、构造矩阵：
第i个行点与第j个列点的流量即为(i,j)的值
代码：
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 // const int maxn = 0; 23 // const int maxm = 0; 24 // const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 33 /** 34 *最大流最小割：加各种优化的Dinic算法($O(V^2E)$) 35 *输入：图(链式前向星),n(顶点个数,包含源汇),st(源),ed(汇) 36 *输出：Dinic(NdFlow)(最大流),MinCut()(最小割)(需先求最大流) 37 *打印路径方法：按反向边(i&1)的flow 找，或者按边的flow找 38 */ 39 const int maxn = 810; 40 const int maxm = 400010; 41 const int inf = 0x3f3f3f3f; 42 struct Edge 43 { 44 int u, v; 45 int cap, flow; 46 int next; 47 } edge[maxm]; 48 int head[maxn], en; //需初始化 49 int n, m, d[maxn], cur[maxn]; 50 int st, ed; 51 bool vis[maxn]; 52 void addse(int u, int v, int cap, int flow) 53 { 54 edge[en].u = u; 55 edge[en].v = v; 56 edge[en].cap = cap; 57 edge[en].flow = flow; 58 edge[en].next = head[u]; 59 head[u] = en++; 60 cur[u] = head[u]; 61 } 62 void adde(int u, int v, int cap) 63 { 64 addse(u, v, cap, 0); 65 addse(v, u, 0, 0); //注意加反向0边 66 } 67 bool BFS() 68 { 69 queue<int> Q; 70 memset(vis, 0, sizeof(vis)); 71 Q.push(st); 72 d[st] = 0; 73 vis[st] = 1; 74 while (!Q.empty()) 75 { 76 int u = Q.front(); 77 Q.pop(); 78 for (int i = head[u]; i != -1; i = edge[i].next) 79 { 80 int v = edge[i].v; 81 int w = edge[i].cap - edge[i].flow; 82 if (w > 0 && !vis[v]) 83 { 84 vis[v] = 1; 85 Q.push(v); 86 d[v] = d[u] + 1; 87 if (v == ed) return 1; 88 } 89 } 90 } 91 return false; 92 } 93 int Aug(int u, int a) 94 { 95 if (u == ed) return a; 96 int aug = 0, delta; 97 for (int &i = cur[u]; i != -1; i = edge[i].next) 98 { 99 int v = edge[i].v;100 int w = edge[i].cap - edge[i].flow;101 if (w > 0 && d[v] == d[u] + 1)102 {103 delta = Aug(v, min(a, w));104 if (delta)105 {106 edge[i].flow += delta;107 edge[i ^ 1].flow -= delta;108 aug += delta;109 if (!(a -= delta)) break;110 }111 }112 }113 if (!aug) d[u] = -1;114 return aug;115 }116 int Dinic(int NdFlow)117 {118 int flow = 0;119 while (BFS())120 {121 memcpy(cur, head, sizeof(int) * (n + 1));122 flow += Aug(st, inf);123 /*如果超过指定流量就return 掉*/124 if (NdFlow == inf) continue;125 if (flow > NdFlow) break;126 }127 return flow;128 }129 /*残余网络*/130 void Reduce()131 {132 for (int i = 0; i < en; i++) edge[i].cap -= edge[i].flow;133 }134 /*清空流量*/135 void ClearFlow()136 {137 for (int i = 0; i < en; i++) edge[i].flow = 0;138 }139 /*求最小割*/140 vector<int> MinCut()141 {142 BFS();143 vector<int> ans;144 for (int u = 0; u < n; u++)145 {146 if (!vis[u]) continue;147 for (int i = head[u]; i != -1; i = edge[i].next)148 {149 if (i & 1) continue; /*忽略反向边*/150 int v = edge[i].v;151 int w = edge[i].cap;152 if (!vis[v] && w > 0) ans.push_back(i);153 }154 }155 return ans;156 }157 158 int N, M, K;159 int a[maxn], b[maxn];160 int mtx[410][410];161 void init()162 {163 memset(head, -1, sizeof(head));164 en = 0;165 }166 void input()167 {168 for (int i = 0; i < N; i++)169 scanf("%d", &a[i]);170 for (int i = 0; i < M; i++)171 scanf("%d", &b[i]);172 }173 void debug()174 {175 //176 }177 void build()178 {179 st = 0, ed = 1;180 n = N + M + 2;181 for (int i = 0; i < N; i++)182 {183 adde(st, i + 2, a[i]);184 }185 for (int i = 0; i < M; i++)186 {187 adde(i + N + 2, ed, b[i]);188 }189 for (int i = 0; i < N; i++)190 {191 for (int j = 0; j < M; j++)192 {193 adde(i + 2, j + N + 2, K);194 }195 }196 }197 bool dfsc(int u, int fa)198 {199 vis[u] = 1;200 for (int i = head[u]; ~i; i = edge[i].next)201 {202 int v = edge[i].v;203 if (v == fa || edge[i].flow == edge[i].cap) continue;204 if (vis[v] || dfsc(v, u)) return 1;205 }206 vis[u] = 0;207 return 0;208 }209 bool check()210 {211 memset(vis, 0, sizeof(vis));212 for (int i = 2; i < N + 2; i++)213 {214 if (!vis[i])215 {216 vis[i] = 1;217 if (dfsc(i, i)) return 0;218 vis[i] = 0;219 }220 }221 return 1;222 }223 void solve()224 {225 build();226 Dinic(inf);227 // cout << "flow: " << Dinic(inf) << endl;228 int flag = 1;229 for (int i = head[st]; ~i; i = edge[i].next)230 {231 if (i & 1) continue;232 if (edge[i].cap > edge[i].flow)233 {234 flag = 0;235 break;236 }237 }238 for (int i = head[ed]; ~i; i = edge[i].next)239 {240 if (i & 0) continue;241 if (-edge[i].flow < edge[i ^ 1].flow)242 {243 flag = 0;244 break;245 }246 }247 if (!flag)248 {249 puts("Impossible");250 return;251 }252 if (!check())253 {254 puts("Not Unique");255 return;256 }257 for (int u = 0; u < N; u++)258 {259 for (int i = head[u + 2]; ~i; i = edge[i].next)260 {261 if (i & 1) continue;262 int v = edge[i].v - N - 2;263 mtx[u][v] = edge[i].flow;264 }265 }266 puts("Unique");267 for (int i = 0; i < N; i++)268 {269 for (int j = 0; j < M; j++)270 {271 if (j < M - 1) printf("%d ", mtx[i][j]);272 else printf("%d\n", mtx[i][j]);273 }274 }275 }276 void output()277 {278 //279 }280 int main()281 {282 // int size = 256 << 20; // 256MB283 // char *p = (char *)malloc(size) + size;284 // __asm__("movl %0, %%esp\n" :: "r"(p));285 286 // std::ios_base::sync_with_stdio(false);287 #ifndef ONLINE_JUDGE288 freopen("in.cpp", "r", stdin);289 #endif290 291 while (~scanf("%d%d%d", &N, &M, &K))292 {293 init();294 input();295 solve();296 output();297 }298 return 0;299 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。