Artifact bbf018ad57eb14ba36a59110855312071394ec5a

• File SRM/334/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;

typedef int cost;
typedef int vert;
typedef vector< vector<cost> > graph;

cost bidi_minCut( graph G, int N)
{
	vector<vert> V;
	for(int v=0; v<N; ++v)
		V.push_back(v);

	cost result = 0x7fffffff;
	for(int n=N; n>1; --n)
	{
		// invariant:
		//   the current set of vertices = {V[0] .. V[n-1]}

		// order the vertices
		vector<int> vs;
		cost lastCut = 0;
		{
			vector<cost> ws(n, 0);
			ws[0] = 1;

			for(int i=0; i<n; ++i) {
				int j = max_element(ws.begin(), ws.end()) - ws.begin();
				lastCut = ws[j];

				vs.push_back(j);
				ws[j] = -1;
				for(int k=0; k<n; ++k)
					if( ws[k] != -1 )
						ws[k] += G[V[k]][V[j]];
			}
		}

		// update mincut
		result = min(result, lastCut);

		// reduce the graph (unify vs[n-2] and vs[n-1])
		vert v2=vs[n-2], v1=vs[n-1];
		for(int i=0; i<n; ++i) {
			G[V[v2]][V[i]] += G[V[v1]][V[i]];
			G[V[i]][V[v2]] += G[V[i]][V[v1]];
		}
		V.erase( V.begin() + v1 );
	}
	return result;
}

class Terrorists
{
public:
	int requiredCost(vector <string> roads) 
	{
		int N = roads.size();
		graph G(N, vector<cost>(N));

		for(int i=0; i<N; ++i)
		for(int j=0; j<N; ++j)
			G[i][j] = roads[i][j]-'0';

		return bidi_minCut(G, N);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	string roads_[] = {"0911",
 "9011",
 "1109",
 "1190"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	int RetVal = 4; 
	return verify_case(RetVal, Terrorists().requiredCost(roads)); }
int Test_(Case_<1>) {
	string roads_[] = {"0399",
 "3033",
 "9309",
 "9390"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	int RetVal = 9; 
	return verify_case(RetVal, Terrorists().requiredCost(roads)); }
int Test_(Case_<2>) {
	string roads_[] = {"030900",
 "304120",
 "040174",
 "911021",
 "027207",
 "004170"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	int RetVal = 8; 
	return verify_case(RetVal, Terrorists().requiredCost(roads)); }
int Test_(Case_<3>) {
	string roads_[] = {"044967263",
 "409134231",
 "490642938",
 "916036261",
 "634306024",
 "742660550",
 "229205069",
 "633625604",
 "318140940"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	int RetVal = 27; 
	return verify_case(RetVal, Terrorists().requiredCost(roads)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE