Network Mess

[問題] 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 }