| ||||||||||
| 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