Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

RE求解释, 请大神们帮忙看一下

Posted by bestofme at 2014-04-30 22:33:16 on Problem 2516
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator