Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
RE求解释, 请大神们帮忙看一下#include <queue> #include <cstdio> #include <cstring> using namespace std; const int INF = 2000000000; const int N = 512; int V; int cap[N][N]; int cost[N][N]; int d[N]; int p[N]; bool inq[N]; queue<int> q; struct MinCostMaxFlow { MinCostMaxFlow(int n) { V = n; memset(cap, 0, sizeof(cap)); } void AddEdge(int u, int v, int c, int w) { cap[u][v] = c, cost[u][v] = w; cap[v][u] = 0, cost[v][u] = -w; } pair<int, int> GetMaxFlow(int s, int t) { int totflow = 0, totcost = 0; while (true) { for (int i = 0; i < V; i++) { d[i] = INF; } d[s] = 0; memset(inq, false, V); q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int v = 0; v < V; v++) { int c = cap[u][v]; int w = cost[u][v]; if (c > 0 && d[v] > d[u] + w) { d[v] = d[u] + w; p[v] = u; if (!inq[v]) { q.push(v), inq[v] = true; } } } } if (d[t] == INF) break; int amt = INF; for (int u = t; u != s; u = p[u]) { int c = cap[p[u]][u]; if (amt > c) amt = c; } for (int u = t; u != s; u = p[u]) { cap[p[u]][u] -= amt; cap[u][p[u]] += amt; } totflow += amt, totcost += d[t] * amt; } return make_pair(totflow, totcost); } }; int main() { int n, m, k; while (scanf("%d%d%d", &n, &m, &k) != EOF) { if (n == 0 && m == 0 && k == 0) break; int s = 0, t = (m+n)*k + 1; int off = m*k; int need = 0; MinCostMaxFlow solver = MinCostMaxFlow(t+1); for (int i = 0; i < n; i++) { int off1 = off + i * k; for (int j = 1; j <= k; j++) { int c; scanf("%d", &c); solver.AddEdge(off1+j, t, c, 0); need += c; } } for (int i = 0; i < m; i++) { int off2 = i * k; for (int j = 1; j <= k; j++) { int c; scanf("%d", &c); solver.AddEdge(s, off2+j, c, 0); } } for (int x = 1; x <= k; x++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int a = j * k + x; int b = off + i * k + x; int w; scanf("%d", &w); solver.AddEdge(a, b, INF, w); } } } pair<int, int> pii = solver.GetMaxFlow(s, t); int maxflow = pii.first, mincost = pii.second; if (maxflow < need) printf("-1\n"); else printf("%d\n", mincost); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator