首页 > 代码库 > POJ 2516 Minimum Cost(费用流)
POJ 2516 Minimum Cost(费用流)
POJ 2516 Minimum Cost
题目链接
题意:转一篇题意吧。。感觉写的很详细了,優YoU http://blog.csdn.net/lyy289065406/article/details/6742534
思路:一开始是把所有商家的每种物品和所有供应商所有物品连边跑费用流,结果TLE了,因为这样建出来的图,边数会非常的庞大
那么其实转化一下思路,每种物品之间是不会互相影响的,那么把每种物品求出来后,累加起来就是答案了,然后注意这题数据要读完,直接判断错没读完数据就会WA
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXNODE = 5005; const int MAXEDGE = 500005; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type cap, flow, cost; Edge() {} Edge(int u, int v, Type cap, Type flow, Type cost) { this->u = u; this->v = v; this->cap = cap; this->flow = flow; this->cost = cost; } }; struct MCFC { int n, m, s, t; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; int inq[MAXNODE]; Type d[MAXNODE]; int p[MAXNODE]; Type a[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type cap, Type cost) { edges[m] = Edge(u, v, cap, 0, cost); next[m] = first[u]; first[u] = m++; edges[m] = Edge(v, u, 0, 0, -cost); next[m] = first[v]; first[v] = m++; } bool bellmanford(int s, int t, Type &flow, Type &cost) { for (int i = 0; i < n; i++) d[i] = INF; memset(inq, false, sizeof(inq)); d[s] = 0; inq[s] = true; p[s] = s; a[s] = INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (e.cap > e.flow && d[e.v] > d[u] + e.cost) { d[e.v] = d[u] + e.cost; p[e.v] = i; a[e.v] = min(a[u], e.cap - e.flow); if (!inq[e.v]) {Q.push(e.v); inq[e.v] = true;} } } } if (d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; int u = t; while (u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].u; } return true; } Type Mincost(int s, int t, Type sum) { Type flow = 0, cost = 0; while (bellmanford(s, t, flow, cost)); if (sum != flow) cost = -1; return cost; } } gao; const int N = 55; int n, m, k, sum; int a[N][N], b[N][N]; int solve() { int c, ans = 0, flag = 0; for (int i = 0; i < k; i++) { gao.init(n + m + 2); for (int j = 1; j <= m; j++) gao.add_Edge(0, j, b[j][i], 0); int sum = 0; for (int j = 1; j <= n; j++) { sum += a[j][i]; gao.add_Edge(m + j, n + m + 1, a[j][i], 0); } for (int x = 1; x <= n; x++) { for (int y = 1; y <= m; y++) { scanf("%d", &c); gao.add_Edge(y, x + m, INF, c); } } if (flag) continue; int tmp = gao.Mincost(0, n + m + 1, sum); if (tmp == -1) flag = 1; else ans += tmp; } if (flag) ans = -1; return ans; } int main() { while (~scanf("%d%d%d", &n, &m, &k) && n) { for (int i = 1; i <= n; i++) for (int j = 0; j < k; j++) scanf("%d", &a[i][j]); for (int i = 1; i <= m; i++) for (int j = 0; j < k; j++) scanf("%d", &b[i][j]); printf("%d\n", solve()); } return 0; }
POJ 2516 Minimum Cost(费用流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。