Network Mess
2007.08.24 22:29 ACM/ICPC 2005
[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem G
[解説]
詳細は後日書きたいと思います。
[サンプルプログラム]
[解説]
詳細は後日書きたいと思います。
[サンプルプログラム]
001 #include<iostream> 002 #include<vector> 003 #include<queue> 004 #include<algorithm> 005 using namespace std; 006 #define MAX 50 007 #define NMAX 80 008 009 class Node{ 010 public: 011 vector<int> adjList; 012 Node(){} 013 void insert( int i ){ adjList.push_back(i);} 014 }; 015 016 class Network{ 017 public: 018 vector<Node> nodes; 019 Network(){} 020 021 int size(){ return nodes.size(); } 022 void addNode(){ nodes.push_back(Node()); } 023 024 void connect( int i, int j ){ 025 nodes[i].insert(j); nodes[j].insert(i); 026 } 027 028 void addNewNodes( int target, int diff, int u ){ 029 if ( diff == 1 ){ 030 connect( target, u ); 031 } else { 032 for ( int i = 1; i < diff; i++ ){ 033 addNode(); 034 if ( i == 1 ) connect( target, size()-1 ); 035 else connect( size()-2, size()-1); 036 } 037 connect( size()-1, u ); 038 } 039 } 040 }; 041 042 class State{ 043 public: 044 int cur, pre, d; 045 State(){} 046 State(int cur, int pre, int d): cur(cur), pre(pre), d(d){} 047 }; 048 049 int N, M[MAX][MAX]; 050 Network network; 051 052 int getDistance(int s, int t){ 053 queue<State> Q; 054 Q.push(State(s, -1, 0)); 055 State u; 056 while( !Q.empty() ){ 057 u = Q.front(); Q.pop(); 058 if ( u.cur == t ) return u.d; 059 for ( int i = 0; i < network.nodes[u.cur].adjList.size(); i++ ){ 060 int v = network.nodes[u.cur].adjList[i]; 061 if ( v != u.pre ){ 062 Q.push(State(v, u.cur, u.d + 1)); 063 } 064 } 065 } 066 } 067 068 int parse( int source, int end ){ 069 int pre = M[end+1][0] - getDistance( source, 0 ); 070 int d; 071 for ( int t = 1; t <= end; t++ ){ 072 d = M[end+1][t] - getDistance( source, t ); 073 if ( pre != d ) return -1; 074 } 075 return pre; 076 } 077 078 void addNewNode( int u ){ 079 for ( int target = N; target < network.size(); target++ ){ 080 int diff = parse(target, u - 1); 081 if ( diff > 0 ) { 082 network.addNewNodes(target, diff, u); 083 return; 084 } 085 } 086 } 087 088 void compute(){ 089 network = Network(); 090 for ( int i = 0; i < N + 1; i++ ) network.addNode(); 091 network.connect( 0, network.size()-1); 092 093 for ( int i = 1; i < N; i++ ) addNewNode(i); 094 095 vector<int> degree; 096 for ( int i = N; i < network.size(); i++ ) { 097 degree.push_back(network.nodes[i].adjList.size()); 098 } 099 sort(degree.begin(), degree.end()); 100 101 for ( int i = 0; i < degree.size(); i++ ){ 102 if ( i ) cout << " "; 103 cout << degree[i]; 104 } 105 cout << endl; 106 } 107 108 bool input(){ 109 cin >> N; 110 if ( N == 0 ) return false; 111 for ( int i = 0; i < N; i++ ){ 112 for ( int j = 0; j < N; j++ ) cin >> M[i][j]; 113 } 114 return true; 115 } 116 117 main(){ 118 while ( input() ) compute(); 119 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |