2357.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2357 on 2006-10-13 at 12:46:05 */
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
typedef long long int64;
typedef pair<int, int64> pii;
const int N = 512;
const int INF = 1 << 28;
const int64 PINF = 1LL << 60;
 
class Heap {
private:
	int size, p[N], h[N];
	int64 d[N];
	void siftUp(int);
	void siftDown(int);
public:
	void clear() { size = 0; memset(h, -1, sizeof(h)); }
	bool isEmpty() const { return (size == 0); }
	void push(int, int64);
	pii pop();
};
void Heap::siftUp(int n) {
	int pn = p[n], i = n;
	int64 dn = d[n];
	while(i > 0 && dn < d[(i-1)/2]) {
		d[i] = d[(i-1)/2]; p[i] = p[(i-1)/2]; h[p[i]] = i;
		i = (i - 1) / 2;
	}
	d[i] = dn; p[i] = pn; h[pn] = i;
}
void Heap::siftDown(int n) {
	int pn = p[n], i = n;
	int64 dn = d[n];
	while(2*i+2 <= size) {
		int m = 2*i+1;
		if(m+1 < size && d[m] > d[m+1]) m++;
		if(dn <= d[m]) break;
		d[i] = d[m]; p[i] = p[m]; h[p[i]] = i;
		i = m;
	}
	d[i] = dn; p[i] = pn; h[pn] = i;
}
void Heap::push(int e, int64 ev) {
	if(h[e] == -1) {
		h[e] = size++; d[h[e]] = ev; p[h[e]] = e;
		siftUp(h[e]);
	} else if(h[e] != -2 && d[h[e]] > ev) {
		d[h[e]] = ev;
		siftUp(h[e]);
	}
}
pii Heap::pop() {
	pii b = pii(p[0], d[0]);
	h[p[0]] = -2;
	if(--size != 0) {
		d[0] = d[size]; p[0] = p[size]; h[p[0]] = 0;
		siftDown(0);
	}
	return b;
}
 
Heap Q;
 
class Edge {
public:
	int u, v, cuv, cvu, flow;
	Edge() {}
	Edge(int cu, int cv, int ccu, int ccv) : u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0) {}
	int other(int p) const { return p == u ? v : u; }
	int cap(int p) const { return p == u ? cuv-flow : cvu+flow; }
	void addFlow(int p, int f) { flow += (p == u ? f : -f); }
};
 
class NodeList {
private:
	int level, next[N], index[2*N], v;
public:
	void clear(int cv) { v = cv; level = -1; memset(index, -1, sizeof(index)); }
	void insert(int n, int h) { next[n] = index[h]; index[h] = n; level >?= h; }
	int remove();
	bool empty() const { return level < 0; }
};
int NodeList::remove() {
	int r = index[level]; index[level] = next[index[level]];
	while(level >= 0 && index[level] == -1) level--;
	return r;
}
 
class Network {
private:
	vector<Edge> eg;
	vector<Edge*> net[N];
	int v, s, t;
	int h[N], hn[2*N], cur[N], e[N];
	int cwn[N], cwlmt[N], fulf;
	NodeList list;
	vector<pii> g[N];
	void initNet();
	void initFlow();
	void initHeight();
	void gapHeuristic(int);
	void push(int);
	void relabel(int);
	void discharge(int);
	void dijkstra(int);
	void initNetwork(int64);
	int maxFlow(int, int);
public:
	int n;
	int64 d[N][N];
	bool build();
	bool fullFlow(int64 midv) { initNetwork(midv); return fulf == maxFlow(0, 1); }
};
void Network::gapHeuristic(int k) {
	if(hn[k] != 0 || k >= v+1) return;
	for(int i = 0; i < v; i++)
		if(h[i] > k && h[i] <= v && i != s)
			{ hn[h[i]]--; hn[v+1]++; h[i] = v+1; }
}
void Network::initNet() {
	for(int i = 0; i < v; i++) net[i].clear();
	for(int i = eg.size()-1; i >= 0; i--) {
		net[eg[i].u].push_back(&eg[i]);
		net[eg[i].v].push_back(&eg[i]);
	}
}
void Network::initHeight() {
	memset(h, 0, sizeof(h)); memset(hn, 0, sizeof(hn));
	memset(e, 0, sizeof(e)); e[s] = INF;
	for(int i = 0; i < v; i++) h[i] = v;
	queue<int> Q; Q.push(t); h[t] = 0;
	while(!Q.empty()) {
		int p = Q.front(); Q.pop();
		for(int i = net[p].size()-1; i >= 0; i--) {
			int u = net[p][i]->other(p), ec = net[p][i]->cap(u);
			if(ec != 0 && h[u] == v && u != s) { h[u] = h[p]+1; Q.push(u); }
		}
	}
	for(int i = 0; i < v; i++) hn[h[i]]++;
}
void Network::initFlow() {
	initNet(); initHeight();
	for(int i = 0; i < v; i++) cur[i] = net[i].size()-1;
	list.clear(v);
	for(; cur[s] >= 0; cur[s]--) push(s);
}
void Network::push(int u) { 
	Edge* te = net[u][cur[u]];
	int ex = min(te->cap(u), e[u]), p = te->other(u);
	if(e[p] == 0 && p != t) list.insert(p, h[p]);
	te->addFlow(u, ex); e[u] -= ex; e[p] += ex; 
} 
void Network::relabel(int u) { 
	int mh = 2*v, oh = h[u]; 
	for(int i = net[u].size()-1; i >= 0; i--) { 
		int p = net[u][i]->other(u); 
		if(net[u][i]->cap(u) != 0) mh <?= h[p]+1; 
	} 
	hn[h[u]]--; hn[mh]++; h[u] = mh; cur[u] = net[u].size()-1; 
	gapHeuristic(oh);
}
void Network::discharge(int u) { 
	while(e[u] > 0)
		if(cur[u] < 0) relabel(u);
		else if(net[u][cur[u]]->cap(u) > 0 && h[u] == h[net[u][cur[u]]->other(u)]+1) push(u);
		else cur[u]--;
}
int Network::maxFlow(int ss, int tt) {
	s = ss; t = tt; initFlow();
	while(!list.empty()) {
		int u = list.remove();
		discharge(u);
	}
	return e[t];
}
void Network::dijkstra(int src) {
	Q.clear(); Q.push(src, 0);
	for(int i = 0; i < n; i++) d[src][i] = PINF;
	while(!Q.isEmpty()) {
		pii s = Q.pop();
		int u = s.first; int64 v = s.second;
		d[src][u] = v;
		for(int i = g[u].size()-1; i >= 0; i--) {
			int no = g[u][i].first, nv = g[u][i].second;
			Q.push(no, v+nv);
		}
	}
}
bool Network::build() {
	int m;
	if(scanf("%d %d", &n, &m) != 2) return false;
	v = 2*n+2; fulf = 0;
	for(int i = 0; i < n; i++) scanf("%d %d", cwn+i, cwlmt+i);
	for(int i = 0; i < n; i++)
		if(cwn[i] > cwlmt[i]) fulf += cwn[i]-cwlmt[i];
	for(int i = 0; i < n; i++) g[i].clear();
	for(int i = 0; i < m; i++) {
		int a, b, pv; scanf("%d %d %d", &a, &b, &pv);
		g[a-1].push_back(pii(b-1, pv)); g[b-1].push_back(pii(a-1, pv)); 
 	}
	for(int i = 0; i < n; i++) dijkstra(i);
	return true;
}
void Network::initNetwork(int64 midv) {
	eg.clear();
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(i != j && d[i][j] <= midv) eg.push_back(Edge(2*i+3, 2*j+2, INF, 0));
	for(int i = 0; i < n; i++) eg.push_back(Edge(2*i+2, 2*i+3, cwn[i], 0));
	for(int i = 0; i < n; i++)
		if(cwn[i] > cwlmt[i]) eg.push_back(Edge(0, 2*i+2, cwn[i]-cwlmt[i], 0));
		else if(cwn[i] < cwlmt[i]) eg.push_back(Edge(2*i+2, 1, cwlmt[i]-cwn[i], 0));
}
 
Network net;
int64 s[N*N],	n;
 
int disperse(int64*, int64*);
 
int main()
{
	while(net.build()) {
		for(int i = n = 0; i < net.n; i++)
			for(int j = i; j < net.n; j++)
				s[n++] = net.d[i][j];
		n = disperse(s, s+n);
		int l = 0, h = n;
		while(h != l) {
			int mid = (h+l)/2;
			if(net.fullFlow(s[mid])) h = mid;
			else l = mid+1;
		}
		if(h == n || s[h] == PINF) printf("-1\n");
		else printf("%lld\n", s[l]);
	}
	
	return 0;
}
 
int disperse(int64* b, int64* e)
{
	int n = e-b, dn = 1;
	sort(b, e);
	for(int i = 1; i < n; i++)
		if(b[i] != b[i-1]) b[dn++] = b[i];
	return dn;
}