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) | ↑ページトップ |