1646.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1646 on 2006-08-29 at 18:58:41 */ 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 128;
const int INF = 1 << 28;

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;
   Edge* net[N][2*N];
   int deg[N], nn[N], v, s, t, m;
   int h[N], hn[2*N], e[N], cur[N];
   void initNet();
   void initFlow();
   void push(int);
   void relabel(int);
	void gapHeuristic(int);
	int maxFlow(int, int);
public:
	bool build();
	int lamed();
};
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) h[i] = v+1;
   for(int i = k+1; i <= v; i++)
      { hn[v+1] += hn[i]; hn[i] = 0; }
}
void Network::initNet() {
   memset(nn, 0, sizeof(nn));
   for(int i = eg.size()-1; i >= 0; i--) {
	   net[eg[i].u][nn[eg[i].u]++] = &eg[i];
	   net[eg[i].v][nn[eg[i].v]++] = &eg[i];
		eg[i].flow = 0;
   }
}
void Network::initFlow() {
	initNet();
   memset(h, 0, sizeof(h)); memset(e, 0, sizeof(e));
   memset(hn, 0, sizeof(hn)); hn[v] = 1; hn[0] = v-1;
   h[s] = v; e[s] = INF;
   for(int i = 0; i < v; i++) cur[i] = nn[i]-1;
}
void Network::push(int u) {
   Edge* te = net[u][cur[u]];
   int ex = min(te->cap(u), e[u]), p = te->other(u);
   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 = nn[u]-1; i >= 0; i--) {
      int p = net[u][i]->other(u);
      if(net[u][i]->cap(u) != 0) mh = min(mh, h[p]+1);
   }
   hn[h[u]]--; hn[mh]++; h[u] = mh; cur[u] = nn[u]-1;
   gapHeuristic(oh);
}
bool Network::build() {
	if(scanf("%d %d", &v, &m) != 2) return false;
	v <<= 1; eg.clear();
	memset(deg, 0, sizeof(deg));
	for(int i = 0; i < m; i++) {
		int a, b;
		scanf("\n(%d,%d)", &a, &b);
		eg.push_back(Edge(2*a, 2*b+1, 1, 0));
		eg.push_back(Edge(2*b, 2*a+1, 1, 0));
		deg[a]++; deg[b]++;
	}
	for(int i = 0; i < v/2; i++) eg.push_back(Edge(2*i+1, 2*i, 1, 0));
   return true;
}
int Network::maxFlow(int ss, int tt) {
   s = ss; t = tt; initFlow();
   queue<int> Q; Q.push(s);
   while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      for(; cur[u] >= 0 && e[u] != 0; cur[u]--) {
         int p = net[u][cur[u]]->other(u);
         if(u == s || h[u] == h[p]+1) {
            if(p != t && e[p] == 0) Q.push(p);
            push(u);
         }
      }
      if(e[u] != 0 && u != s) { relabel(u); Q.push(u); }
   }
   return e[t];
}
int Network::lamed() {
	int s = 0, n = v>>1;
	if(m == n*(n-1)/2) return n;
	for(int i = 1; i < n; i++)
		if(deg[s] > deg[i]) s = i;
	int cn = INF;
	for(int t = 0; t < n; t++)
		cn <?= maxFlow(s*2, t*2+1);
	return cn;
}

int main()
{
	Network net;

	while(net.build()) printf("%d\n", net.lamed());
	
	return 0;
}