2390.cpp

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

/* This Code is Submitted by wywcgs for Problem 2390 on 2006-10-12 at 22:18:26 */
#include <cstdio> 
#include <vector> 
#include <queue> 
#include <algorithm> 
using namespace std; 

const int N = 256;
const int PN = 40960;
const int INF = 1 << 28;

class Path {
public:
	int a, b, l;
	void make() { scanf("%d %d %d", &a, &b, &l); a--; b--; }
	bool operator <(const Path& p) const { return l < p.l; }
};

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 Network { 
private: 
   vector<Edge> eg; 
   vector<Edge*> net[N]; 
   Edge* prev[N]; 
   int v, s, t; 
   int h[N], hn[2*N], cur[N]; 
   void initNet(); 
   void initFlow(); 
   void initHeight(); 
   void gapHeuristic(int); 
public: 
   void build(Path*, int, int);
   int maxFlow(int, int); 
}; 
void Network::initHeight() { 
   memset(h, 0, sizeof(h)); memset(hn, 0, sizeof(hn)); 
   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) { h[u] = h[p]+1; Q.push(u); } 
      } 
   } 
   for(int i = 0; i < v; i++) hn[h[i]]++; 
} 
void Network::gapHeuristic(int k) { 
   if(hn[k] != 0) return; 
   for(int i = 0; i < v; i++) 
      if(h[i] > k) h[i] = v; 
   for(int i = k; i < v; i++) 
      { hn[v] += hn[i]; hn[i] = 0; } 
} 
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::initFlow() { 
   initNet(); initHeight(); 
   for(int i = 0; i < v; i++) cur[i] = net[i].size()-1; 
} 
void Network::build(Path* p, int n, int vn) {
	v = vn; eg.clear();
	for(int i = 0; i <= n; i++) eg.push_back(Edge(p[i].a, p[i].b, 1, 1));
}
int Network::maxFlow(int ss, int tt) { 
   s = ss; t = tt; initFlow(); 
   int c = s, pre[N], flow = 0; 
   pre[s] = -1; 
   while(h[s] < v) { 
      for(; cur[c] >= 0; cur[c]--) 
         if(net[c][cur[c]]->cap(c) != 0 && h[c] == h[net[c][cur[c]]->other(c)]+1) break; 
      if(cur[c] < 0) { 
         int mh = INF, oh = h[c]; 
         for(int i = net[c].size()-1; i >= 0; i--) 
            if(net[c][i]->cap(c) != 0) mh <?= h[net[c][i]->other(c)]; 
         if(mh == INF) h[c] = v; 
         else { h[c] = mh+1; cur[c] = net[c].size()-1; } 
         hn[oh]--; hn[h[c]]++; gapHeuristic(oh); 
         if(c != s) c = pre[c]; 
      } else { 
         int p = net[c][cur[c]]->other(c); 
         prev[p] = net[c][cur[c]]; 
         pre[p] = c; c = p; 
         if(c == t) { 
            int ex = INF; 
            for(; c != s; c = pre[c]) ex <?= prev[c]->cap(pre[c]); 
            for(c = t; c != s; c = pre[c]) prev[c]->addFlow(pre[c], ex); 
            flow += ex; c = s; 
         } 
      } 
   } 
   return flow; 
} 

int main()
{
	Network net;
	int n, m, pt;
	Path p[PN];
	
	while(scanf("%d %d %d", &n, &m, &pt) != EOF) {
		for(int i = 0; i < m; i++) p[i].make();
		sort(p, p+m);
		int h = m-1, l = 0;
		while(h != l) {
			int mid = (l+h)/2;
			net.build(p, mid, n);
			int k = net.maxFlow(0, n-1);
			if(k >= pt) h = mid;
			else l = mid+1;
		}
		printf("%d\n", p[h].l);
	}
	
	return 0;
}