2113.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2113 on 2006-04-14 at 16:50:34 */ 
#include <cstdio>
#include <cstring>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int MAX = 256;
const int INF = 2000000;
const int CITY_CODE_A = 104729;
const int CITY_CODE_B = 95050;

class Network {
private:
	int size, h[MAX], e[MAX], cnth[MAX*2];
	vector<pii> n[MAX];
	vector<pii>::iterator current[MAX];
	void initFlow(int, int);
	void insert(int, int, int);
	void push(int);
	void relabel(int);
	void discharge(int);
	void gapHeuristic(int);
public:
	int road[MAX][MAX], cost[MAX][MAX];
	void clear(int);
	void build(int, int);
	int maxFlow(int, int);
	pii dijkstra();
};
void Network::clear(int n) {
	int i, j;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			cost[i][j] = road[i][j] = INF;
	size = n;
}
void Network::build(int mid, int g) {
	int i, j;
	for(i = 0; i < size; i++) n[i].clear();
	for(i = 0; i < size; i++)
		for(j = 0; j < size; j++)
			if(road[i][j] != INF)
				n[i].push_back(pii(j, (cost[i][j] > mid) ? g+1 : 1));
}
void Network::insert(int u, int v, int ex) {
	vector<pii>::iterator it;
	for(it = n[u].begin(); it != n[u].end(); it++)
		if(it->first == v) { it->second += ex; return; }
	n[u].push_back(pii(v, ex));
}
void Network::push(int u) {
	int v = current[u]->first, &cap = current[u]->second, ex = min(cap, e[u]);
	e[u] -= ex; e[v] += ex; cap -= ex; insert(v, u, ex);
}
void Network::relabel(int u) {
	vector<pii>::iterator it; int mh = INF;
	for(it = n[u].begin(); it != n[u].end(); it++) 
		if(it->second > 0) mh = min(mh, h[it->first]);
	if(--cnth[h[u]] == 0) gapHeuristic(h[u]);
	h[u] = mh + 1; cnth[h[u]]++;
}
void Network::discharge(int u) {
	while(e[u] > 0)
		if(current[u] == n[u].end()) { relabel(u); current[u] = n[u].begin(); }
		else if(current[u]->second > 0 && h[u] == h[current[u]->first] + 1) push(u);
		else current[u]++;
}
void Network::initFlow(int s, int t) {
	memset(h, 0, sizeof(h)); h[s] = size;
	memset(e, 0, sizeof(e));
	memset(cnth, 0, sizeof(cnth)); cnth[size] = 1; cnth[0] = size-1;
	vector<pii>::iterator it;
	for(it = n[s].begin(); it != n[s].end(); it++) { 
		int v = it->first, cap = it->second;
		e[s] -= cap; e[v] += cap;
		insert(v, s, cap); cap = 0;
	}
}
void Network::gapHeuristic(int k) {
	if(k >= size+1) return;
	int i;
	for(i = 0; i < size; i++)
		if(h[i] > k && h[i] < size+1 && i != 0) {
			cnth[h[i]]--; h[i] = size+1; cnth[size+1]++;
		}
}
int Network::maxFlow(int s, int t) {
	initFlow(s, t);
	int i; list<int> L;
	for(i = 0; i < size; i++) {
		current[i] = n[i].begin();
		if(i != s && i != t) L.push_back(i);
	}
	list<int>::iterator u;
	for(u = L.begin(); u != L.end(); u++) {
		int oh = h[*u];
		discharge(*u);
		if(oh != h[*u]) { L.push_front(*u); L.erase(u); u = L.begin(); }
	}
	return e[t];
}
pii Network::dijkstra() {
	int o, i, j;
	int d[2][MAX];
	for(o = 0; o < 2; o++) {
		int src = ((o == 0) ? 0 : size-1);
		bool visit[MAX];
		for(i = 0; i < size; i++)
			d[o][i] = INF, visit[i] = false;
		d[o][src] = 0;
		for(i = 0; i < size; i++) {
			int mind = INF, mini;
			for(j = 0; j < size; j++)
				if(!visit[j] && mind > d[o][j])
					mind = d[o][j], mini = j;
			if(mind == INF) break;
			else {
				visit[mini] = true;
				for(j = 0; j < size; j++)
					if(!visit[j] && d[o][j] > d[o][mini]+road[mini][j])
						d[o][j] = d[o][mini]+road[mini][j];
			}
		}
	}
	int mh = 0, ml = INF, k;
	for(i = 0; i < size; i++)
		for(j = i+1; j < size; j++)
			if(road[i][j] != INF) {
				int p = INF;
				for(k = 0; k < 4; k++) {
					int ca = d[0][(k&1)?i:j], cb = d[1][(k&2)?i:j];
					if(k == 1 || k == 2)
						ca = max(ca, (ca+cb+road[i][j])/2);
					ca = max(ca, cb); p = min(p, ca);
				}
				cost[i][j] = cost[j][i] = p;
				mh = max(mh, p); ml = min(ml, p);
			}
	return pii(ml, mh);
}

inline int code(int, int);

int main()
{
	int i, n, g, e;
	Network net;
	char line[MAX];

	while(gets(line) != NULL && strcmp(line, "0")) {
		sscanf(line, "%d %d %d", &n, &g, &e);
		n += 2; net.clear(n);
		for(i = 0; i < e; i++) {
			int a, b, time;
			scanf("%d %d %d\n", &a, &b, &time);
			a = code(a, n); b = code(b, n);
			net.road[a][b] = net.road[b][a] = 2 * time;
		}
		pii mc = net.dijkstra();
		int l = mc.first, h = mc.second+1;
		while(h != l) {
			int mid = (h + l) / 2;
			net.build(mid, g);
			if(net.maxFlow(0, n-1) > g) l = mid + 1;
			else h = mid;
		}
		if(h == mc.second+1) printf("Impossible\n");
		else printf("%.1lf\n", (double)h/2);
	}

	return 0;
}

inline int code(int num, int n)
{
	switch(num) {
	case CITY_CODE_A: return 0;
	case CITY_CODE_B: return n-1;
	default:          return num+1;
	}
}