首页 > 代码库 > hdu - 4975 - A simple Gaussian elimination problem.(最大流)
hdu - 4975 - A simple Gaussian elimination problem.(最大流)
题意:给一个N行M列的数字矩阵的行和以及列和,每个元素的大小不超过9,问这样的矩阵是否存在,是否唯一N(1 ≤ N ≤ 500) , M(1 ≤ M ≤ 500)。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4975
——>>方法如:http://blog.csdn.net/scnu_jiechao/article/details/40658221
先做hdu - 4888,再来做此题的时候,感觉这题好 SB 呀,将代码提交后自己就 SB 了,咋 TLE 了??
此题卡时间比较严。。可以在判环的地方优化一下4888的代码,因为原选建好的图中的行到列的边,在判环的时候,每条边会被判 (N - 1) * (M - 1) + 1 次,如果先对残量网络重新建图,那么就只会在建图的时候被判一次,差距甚远!
注:输入开挂会RE,猜想输入数据中有负数。。
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using std::min; using std::queue; const int MAXN = 500 * 2 + 10; const int MAXM = 500 * 500 + 2 * MAXN; const int INF = 0x3f3f3f3f; struct EDGE { int from; int to; int cap; int flow; int nxt; } edge[MAXM << 1]; int N, M, kase; int sum; int S, T; int hed[MAXN], ecnt; int cur[MAXN], h[MAXN]; bool impossible, bUnique; void Init() { impossible = false; bUnique = true; ecnt = 0; memset(hed, -1, sizeof(hed)); } void AddEdge(int u, int v, int cap) { edge[ecnt].from = u; edge[ecnt].to = v; edge[ecnt].cap = cap; edge[ecnt].flow = 0; edge[ecnt].nxt = hed[u]; hed[u] = ecnt++; edge[ecnt].from = v; edge[ecnt].to = u; edge[ecnt].cap = 0; edge[ecnt].flow = 0; edge[ecnt].nxt = hed[v]; hed[v] = ecnt++; } bool Bfs() { memset(h, -1, sizeof(h)); queue<int> qu; qu.push(S); h[S] = 0; while (!qu.empty()) { int u = qu.front(); qu.pop(); for (int e = hed[u]; e != -1; e = edge[e].nxt) { int v = edge[e].to; if (h[v] == -1 && edge[e].cap > edge[e].flow) { h[v] = h[u] + 1; qu.push(v); } } } return h[T] != -1; } int Dfs(int u, int cap) { if (u == T || cap == 0) return cap; int flow = 0, subFlow; for (int e = cur[u]; e != -1; e = edge[e].nxt) { cur[u] = e; int v = edge[e].to; if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edge[e].cap - edge[e].flow))) > 0) { flow += subFlow; edge[e].flow += subFlow; edge[e ^ 1].flow -= subFlow; cap -= subFlow; if (cap == 0) break; } } return flow; } int Dinic() { int maxFlow = 0; while (Bfs()) { memcpy(cur, hed, sizeof(hed)); maxFlow += Dfs(S, INF); } return maxFlow; } int ReadInt() { int ret = 0; char ch; while ((ch = getchar()) && ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; } return ret; } void Read() { int r, c; int rsum = 0, csum = 0; scanf("%d%d", &N, &M); S = 0; T = N + M + 1; getchar(); for (int i = 1; i <= N; ++i) { // r = ReadInt(); scanf("%d", &r); rsum += r; AddEdge(S, i, r); } for (int i = 1; i <= M; ++i) { // c = ReadInt(); scanf("%d", &c); csum += c; AddEdge(i + N, T, c); } if (rsum != csum) { impossible = true; return; } sum = rsum; for (int i = 1; i <= N; ++i) { for (int j = M; j >= 1; --j) { AddEdge(i, j + N, 9); } } } void CheckPossible() { if (impossible) return; if (Dinic() != sum) { impossible = true; } } void AddEdge(int u, int v) { edge[ecnt].to = v; edge[ecnt].nxt = hed[u]; hed[u] = ecnt++; } void ReBuild() { memset(hed, -1, sizeof(hed)); int total = ecnt; ecnt = 0; for (int e = 0; e < total; ++e) { if (edge[e].cap > edge[e].flow) { AddEdge(edge[e].from, edge[e].to); } } } bool vis[MAXN]; bool CheckCircle(int x, int f) { vis[x] = true; for (int e = hed[x]; e != -1; e = edge[e].nxt) { int v = edge[e].to; if (v != f) { if (vis[v]) return true; if (CheckCircle(v, x)) return true; } } vis[x] = false; return false; } void CheckUnique() { if (impossible) return; memset(vis, 0, sizeof(vis)); for (int i = 1; i <= N; ++i) { if (CheckCircle(i, -1)) { bUnique = false; return; } } } void Output() { printf("Case #%d: ", ++kase); if (impossible) { puts("So naive!"); } else if (bUnique) { puts("So simple!"); } else { puts("So young!"); } } int main() { int T; scanf("%d", &T); while (T--) { Init(); Read(); CheckPossible(); ReBuild(); CheckUnique(); Output(); } return 0; }
hdu - 4975 - A simple Gaussian elimination problem.(最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。