Artifact Content
Not logged in

Artifact 8d99ffa6917f3084496b33784762562937300111


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

static const int NV = 256;
typedef int           flow;
typedef int           cost;
typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;
typedef flow          flow_graph[NV][NV];
typedef cost          cost_graph[NV][NV];
static const flow FLOW_INF = 0x7FFFFFFF;
static const cost COST_INF = 0x7FFFFFFF;

// edges(bidi), capacity, cost(s.t. C[x][y]=-C[y][x]) per 1 flow, src, dst
pair<cost,flow> mincostFlow(graph& G, flow_graph F, cost_graph C, vert S, vert D)
{
	int N = G.size();
	cost total_cost = 0;
	flow total_flow = 0;

	vector<cost> h(N, 0); // potential
	for(cost RF=FLOW_INF; RF>0; ) // residual flow
	{
		// Dijkstra -- find the min-cost path
		vector<cost> d(N, COST_INF);  d[S] = 0;
		vector<vert> prev(N, -1);

		typedef pair<cost, pair<vert,vert> > cedge;
		priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
		Q.push( cedge(0, make_pair(S,S)) );
		while( !Q.empty() ) {
			cedge e = Q.top(); Q.pop();
			if( prev[e.second.second] >= 0 )
				continue;
			prev[e.second.second] = e.second.first;

			vert u = e.second.second;
			for(int i=0; i<G[u].size(); ++i) {
				vert v = G[u][i];
				cost r_cost = C[u][v] + h[u] - h[v];
				if( F[u][v] > 0 && d[v] > d[u]+r_cost )
					Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
			}
		}

		if( prev[D] < 0 )
			break; // Finished

		// As much as possible
		flow f = RF;
		for(vert u=D; u!=S; u=prev[u])
			f = min(f, F[prev[u]][u]);
		RF         -= f;
		total_flow += f;

		for(vert u=D; u!=S; u=prev[u])
		{
			total_cost    += f * C[prev[u]][u];
			F[prev[u]][u] -= f;
			F[u][prev[u]] += f;
		}

		// Update the potential
		for(vert u=0; u<N; ++u)
			h[u] += d[u];
	}
	return make_pair(total_cost, total_flow);
}

class MarblesRegroupingHard { public:
	int minMoves(vector <string> boxes) 
	{
		const int NB = boxes.size();
		vector< vector<int> > bb(NB);
		for(int i=0; i<boxes.size(); ++i)
		{
			stringstream sin(boxes[i]);
			for(int v; sin>>v; )
				bb[i].push_back(v);
		}
		const int NC = bb[0].size();

		graph G(NB+NC+3);
		flow_graph F = {};
		cost_graph C = {};
		for(int i=0; i<NB; ++i) {
			G[0].push_back(2+i);
			G[2+i].push_back(0);
			F[0][2+i] = 1;
		}
		for(int i=0; i<NC; ++i) {
			G[2+NB+i].push_back(1);
			G[1].push_back(2+NB+i);
			F[2+NB+i][1] = 1;
		}
		{
			G[2+NB+NC].push_back(1);
			G[1].push_back(2+NB+NC);
			F[2+NB+NC][1] = NB-NC;
		}
		for(int i=0; i<NB; ++i)
		for(int j=0; j<NC; ++j) {
			G[2+i].push_back(2+NB+j);
			G[2+NB+j].push_back(2+i);
			F[2+i][2+NB+j] = 1;
			int c = 0;
			for(int k=0; k<NB; ++k) if(k!=i)
				c += bb[k][j];
			C[2+i][2+NB+j] = c;
			C[2+NB+j][2+i] = -c;
		}
		for(int i=0; i<NB; ++i) {
			G[2+i].push_back(2+NB+NC);
			G[2+NB+NC].push_back(2+i);
			F[2+i][2+NB+NC] = 1;
		}
		pair<cost,flow> ff = mincostFlow(G, F, C, 0, 1);
		return ff.first;
	}
};

// 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> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, MarblesRegroupingHard().minMoves(boxes));}
int main(){

CASE(0)
	string boxes_[] = {"0"};
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = 0; 
END
CASE(1)
	string boxes_[] = {"77 97","8 0"};
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = 77; 
END
CASE(2)
	string boxes_[] = {"6 97 7","73 45 0","67 45 63"};
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = 170; 
END
CASE(3)
	string boxes_[] = {"97 94 0 99","1 72 46 45","0 10 47 75","0 92 76 20","2 25 98 22"};
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = 559; 
END
CASE(4)
	string boxes_[] = {"38 0 0 45 77 61 0 0 8 87 65 53 0 2",
 "0 97 79 37 70 0 69 35 95 11 75 96 77 29",
 "39 32 0 24 63 22 91 71 0 63 92 59 12 0",
 "34 0 0 71 88 13 60 56 0 22 29 89 81 53",
 "69 95 65 0 94 98 84 37 0 87 16 0 58 18",
 "82 0 36 88 0 54 82 40 6 0 34 44 80 2",
 "33 58 7 95 83 87 0 0 79 35 0 51 22 84",
 "7 0 30 57 33 4 0 26 44 55 67 31 88 42",
 "62 58 62 93 91 0 1 0 44 23 95 0 55 57",
 "35 8 22 26 76 0 78 54 0 46 42 0 0 64",
 "93 54 58 0 89 89 0 0 57 0 98 3 24 0",
 "9 0 0 23 82 18 0 46 0 0 94 84 19 18",
 "78 12 6 45 0 80 16 69 59 76 35 0 66 0",
 "0 68 77 13 15 0 52 72 0 0 18 65 23 0",
 "0 0 73 53 0 95 91 44 27 96 85 0 99 85",
 "93 29 4 89 27 44 27 17 21 6 0 8 3 91",
 "0 46 73 94 60 59 15 50 18 75 74 88 46 93",
 "0 0 0 94 93 26 21 83 54 62 0 89 59 77",
 "32 98 0 44 34 38 56 20 0 61 29 94 52 57",
 "52 60 0 22 0 5 38 0 50 98 12 75 0 81",
 "23 0 41 18 36 87 49 32 62 43 22 74 0 97",
 "0 0 30 79 16 73 61 0 75 51 64 13 45 0",
 "11 0 14 2 0 1 2 16 84 37 95 45 48 33",
 "10 0 0 35 0 85 28 76 99 74 76 32 52 8",
 "60 0 96 0 95 26 59 13 0 0 44 42 97 48",
 "34 7 77 25 91 85 35 78 32 99 7 29 18 15",
 "61 50 43 22 42 63 64 50 9 94 42 22 21 33",
 "58 0 41 10 16 0 27 67 83 27 14 37 98 47",
 "37 60 60 76 71 2 84 32 27 39 82 84 0 94",
 "15 98 69 82 36 66 0 97 62 39 0 65 62 67",
 "0 41 0 43 0 0 94 0 0 58 0 0 27 33",
 "53 90 71 91 85 0 32 86 40 60 11 0 99 28",
 "79 62 0 0 79 0 14 62 87 76 35 0 70 0",
 "0 40 73 48 0 63 0 0 63 5 30 18 47 51",
 "75 6 58 69 33 57 66 0 12 0 46 0 65 10"};
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = 18618; 
END
/*
CASE(5)
	string boxes_[] = ;
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = ; 
END
CASE(6)
	string boxes_[] = ;
	  vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_)); 
	int _ = ; 
END
*/
}
// END CUT HERE