40c16bd858 2012-04-11 kinaba: #include <iostream> 40c16bd858 2012-04-11 kinaba: #include <sstream> 40c16bd858 2012-04-11 kinaba: #include <iomanip> 40c16bd858 2012-04-11 kinaba: #include <vector> 40c16bd858 2012-04-11 kinaba: #include <string> 40c16bd858 2012-04-11 kinaba: #include <map> 40c16bd858 2012-04-11 kinaba: #include <set> 40c16bd858 2012-04-11 kinaba: #include <algorithm> 40c16bd858 2012-04-11 kinaba: #include <numeric> 40c16bd858 2012-04-11 kinaba: #include <iterator> 40c16bd858 2012-04-11 kinaba: #include <functional> 40c16bd858 2012-04-11 kinaba: #include <complex> 40c16bd858 2012-04-11 kinaba: #include <queue> 40c16bd858 2012-04-11 kinaba: #include <stack> 40c16bd858 2012-04-11 kinaba: #include <cmath> 40c16bd858 2012-04-11 kinaba: #include <cassert> 40c16bd858 2012-04-11 kinaba: #include <cstring> 40c16bd858 2012-04-11 kinaba: #ifdef __GNUC__ 40c16bd858 2012-04-11 kinaba: #include <ext/hash_map> 40c16bd858 2012-04-11 kinaba: #define unordered_map __gnu_cxx::hash_map 40c16bd858 2012-04-11 kinaba: #else 40c16bd858 2012-04-11 kinaba: #include <unordered_map> 40c16bd858 2012-04-11 kinaba: #endif 40c16bd858 2012-04-11 kinaba: using namespace std; 40c16bd858 2012-04-11 kinaba: typedef long long LL; 40c16bd858 2012-04-11 kinaba: typedef complex<double> CMP; 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: static const int INF = 0x3fffffff; 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: typedef int vert; 40c16bd858 2012-04-11 kinaba: typedef vert edge; 40c16bd858 2012-04-11 kinaba: typedef vector<edge> edges; 40c16bd858 2012-04-11 kinaba: typedef vector<edges> graph; 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) 40c16bd858 2012-04-11 kinaba: { 40c16bd858 2012-04-11 kinaba: for(int i=0; i<G[v].size(); ++i) { 40c16bd858 2012-04-11 kinaba: vert u = G[v][i]; 40c16bd858 2012-04-11 kinaba: if( visited[u] ) continue; 40c16bd858 2012-04-11 kinaba: visited[u] = true; 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) 40c16bd858 2012-04-11 kinaba: { matchTo[v]=u, matchTo[u]=v; return true; } 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: return false; 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: template<int NV> 40c16bd858 2012-04-11 kinaba: int biMatch( graph& G, int L ) // [0,L):left, [L,?):right 40c16bd858 2012-04-11 kinaba: // only left->right edges are used during computation 40c16bd858 2012-04-11 kinaba: { 40c16bd858 2012-04-11 kinaba: vector<vert> matchTo(G.size(), -1); 40c16bd858 2012-04-11 kinaba: int ans = 0; 40c16bd858 2012-04-11 kinaba: for(vert v=0; v<L; ++v) { 40c16bd858 2012-04-11 kinaba: bool visited[NV] = {}; 40c16bd858 2012-04-11 kinaba: if( augment(G, v, matchTo, visited) ) 40c16bd858 2012-04-11 kinaba: ++ans; 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: return ans; 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: class SafeReturn { public: 40c16bd858 2012-04-11 kinaba: int minRisk(int N, vector <string> streets) 40c16bd858 2012-04-11 kinaba: { 40c16bd858 2012-04-11 kinaba: int T = streets.size(); 40c16bd858 2012-04-11 kinaba: vector< vector<int> > g(T, vector<int>(T, INF)); 40c16bd858 2012-04-11 kinaba: for(int i=0; i<T; ++i) 40c16bd858 2012-04-11 kinaba: for(int j=0; j<T; ++j) 40c16bd858 2012-04-11 kinaba: if( i == j ) 40c16bd858 2012-04-11 kinaba: g[i][j] = 0; 40c16bd858 2012-04-11 kinaba: else if( streets[i][j] != '-' ) 40c16bd858 2012-04-11 kinaba: g[i][j] = streets[i][j] - '0'; 40c16bd858 2012-04-11 kinaba: vector< vector<int> > d = g; 40c16bd858 2012-04-11 kinaba: for(int k=0; k<T; ++k) 40c16bd858 2012-04-11 kinaba: for(int i=0; i<T; ++i) 40c16bd858 2012-04-11 kinaba: for(int j=0; j<T; ++j) 40c16bd858 2012-04-11 kinaba: d[i][j] = min(d[i][j], d[i][k]+d[k][j]); 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: graph G(2*(N+1)); 40c16bd858 2012-04-11 kinaba: for(int x=0; x<=N; ++x) 40c16bd858 2012-04-11 kinaba: for(int y=0; y<=N; ++y) if( x != y ) 40c16bd858 2012-04-11 kinaba: { 40c16bd858 2012-04-11 kinaba: if( d[0][x] + d[x][y] == d[0][y] ) 40c16bd858 2012-04-11 kinaba: { 40c16bd858 2012-04-11 kinaba: G[x].push_back(N+1+y); 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: return N+1 - biMatch<256>(G, N+1); 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: }; 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: // BEGIN CUT HERE 40c16bd858 2012-04-11 kinaba: #include <ctime> 40c16bd858 2012-04-11 kinaba: double start_time; string timer() 40c16bd858 2012-04-11 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 40c16bd858 2012-04-11 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 40c16bd858 2012-04-11 kinaba: { os << "{ "; 40c16bd858 2012-04-11 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 40c16bd858 2012-04-11 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 40c16bd858 2012-04-11 kinaba: void verify_case(const int& Expected, const int& Received) { 40c16bd858 2012-04-11 kinaba: bool ok = (Expected == Received); 40c16bd858 2012-04-11 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 40c16bd858 2012-04-11 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 40c16bd858 2012-04-11 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 40c16bd858 2012-04-11 kinaba: #define END verify_case(_, SafeReturn().minRisk(N, streets));} 40c16bd858 2012-04-11 kinaba: int main(){ 40c16bd858 2012-04-11 kinaba: 40c16bd858 2012-04-11 kinaba: CASE(0) 40c16bd858 2012-04-11 kinaba: int N = 3; 40c16bd858 2012-04-11 kinaba: string streets_[] = {"-234", 40c16bd858 2012-04-11 kinaba: "2---", 40c16bd858 2012-04-11 kinaba: "3---", 40c16bd858 2012-04-11 kinaba: "4---"}; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = 3; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: CASE(1) 40c16bd858 2012-04-11 kinaba: int N = 2; 40c16bd858 2012-04-11 kinaba: string streets_[] = {"-12", 40c16bd858 2012-04-11 kinaba: "1-1", 40c16bd858 2012-04-11 kinaba: "21-"}; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = 1; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: CASE(2) 40c16bd858 2012-04-11 kinaba: int N = 3; 40c16bd858 2012-04-11 kinaba: string streets_[] = {"-----7", 40c16bd858 2012-04-11 kinaba: "--1---", 40c16bd858 2012-04-11 kinaba: "-1-5--", 40c16bd858 2012-04-11 kinaba: "--5-1-", 40c16bd858 2012-04-11 kinaba: "---1-3", 40c16bd858 2012-04-11 kinaba: "7---3-"}; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = 1; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: CASE(3) 40c16bd858 2012-04-11 kinaba: int N = 2; 40c16bd858 2012-04-11 kinaba: string streets_[] = {"-11", 40c16bd858 2012-04-11 kinaba: "1-1", 40c16bd858 2012-04-11 kinaba: "11-"}; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = 2; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: /* 40c16bd858 2012-04-11 kinaba: CASE(4) 40c16bd858 2012-04-11 kinaba: int N = ; 40c16bd858 2012-04-11 kinaba: string streets_[] = ; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = ; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: CASE(5) 40c16bd858 2012-04-11 kinaba: int N = ; 40c16bd858 2012-04-11 kinaba: string streets_[] = ; 40c16bd858 2012-04-11 kinaba: vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); 40c16bd858 2012-04-11 kinaba: int _ = ; 40c16bd858 2012-04-11 kinaba: END 40c16bd858 2012-04-11 kinaba: */ 40c16bd858 2012-04-11 kinaba: } 40c16bd858 2012-04-11 kinaba: // END CUT HERE