A2.

/************************************************************************/ /* created: 24/3/2004 10:11 */ /* platform: Microsoft Visual C++ v6.0 */ /* filename: Algorithm_A2 */ /* author: SunDrop */ /************************************************************************/ #pragma warning(disable:4786) // VC 版 STL 的一个 bug 。 #include <iostream> #include <iterator> #include <utility> #include <vector> #include <map> #pragma hdrstop using namespace std ; // 漫游规则的定义和初始化。 // 采用map定义在保证效率的同时使之更清晰。 typedef enum Direction { north , east , south , west } ; map < Direction , pair < int , int > > RoamRule ; inline void Init_Rules () { RoamRule.insert( pair < Direction , pair < int , int > > ( north , pair < int , int > ( -1 , 0 ) ) ) ; RoamRule.insert( pair < Direction , pair < int , int > > ( east , pair < int , int > ( 0 , +1 ) ) ) ; RoamRule.insert( pair < Direction , pair < int , int > > ( south , pair < int , int > ( +1 , 0 ) ) ) ; RoamRule.insert( pair < Direction , pair < int , int > > ( west , pair < int , int > ( 0 , -1 ) ) ) ; } ; int bound , step ; // 边界大小 bound 和 跨度限制 step 。 vector < vector < int > > matrix ; // matrix 是读入的钱数矩阵。 vector < vector < int > > backup ; // backup 是计算结果的存储容器。 // －1代表此方格还没有遍历，非负数代表从此点出发所能得到的最大钱数。 int max_gain ( int x , int y ) // 递归函数 max_gain() 。 { // 递归获得从各点出发所能得到的最大钱数，类似动态规划的思想。 int i , j ; int xx , yy ; if ( backup[x][y]>=0 ) return backup[x][y] ; int k=0 , kk ; for ( i=north ; i<=west ; i++ ) { for ( j=1 ; j<=step ; j++ ) { xx=x+RoamRule[Direction(i)].first*j , yy=y+RoamRule[Direction(i)].second*j ; if ( 0<=xx && xx<bound && 0<=yy && yy<bound ) { if ( matrix[xx][yy]>matrix[x][y] ) { kk=max_gain( xx , yy ) ; if ( k<kk ) k=kk ; } } else break ; } } backup[x][y]=matrix[x][y]+k ; return backup[x][y] ; } void main() // 主函数负责数据输入，结果记录和输出工作。 { int m ; char i , j ; vector < int > result_gain ; Init_Rules() ; cout << "Input Please ..." << endl ; // 数据输入 cin >> m ; while ( m-- ) { cin >> bound >> step ; matrix.assign( bound , vector < int > ( bound ) ) ; backup.assign( bound , vector < int > ( bound , -1 ) ) ; for ( i=0 ; i<bound ; i++ ) for ( j=0 ; j<bound ; j++ ) cin >> matrix[i][j] ; result_gain.push_back( max_gain (0,0) ) ; // 递归计算并返回结果，存入结果向量。 } cout << "Output Here Goes ..." << endl ; // 结果数据输出 copy( result_gain.begin() , result_gain.end() , ostream_iterator < int > ( cout , "\n\n" ) ) ; }

A3.

/************************************************************************/ /* created: 24/3/2004 16:01 */ /* platform: Microsoft Visual C++ v6.0 */ /* filename: Algorithm_A3 */ /* author: SunDrop */ /************************************************************************/ #pragma warning(disable:4786) // VC 版 STL 的一个 bug 。 #include <algorithm> #include <stdexcept> #include <iostream> #include <string> #include <vector> #include <deque> #pragma hdrstop using namespace std ; int citynum ; // 城市数 citynum 。 vector < string > citylist ; // 城市名单及其对应城市编号。 vector < int > vp ; // index 与 citylist 对应的城市属性 vp 。 // 表示其是否为关节点。 // 零表示此点不是关节点，非零表示此点是关节点。 vector < vector < bool > > form ; // 城市邻接矩阵。 deque < int > cq ; // 此结点及其所有根结点的队列，亦即目前访问结点的堆栈。 vector < vector < string > > result ; // 结果容器。 void roam( int n ) // 遍历生成树的函数 roam() 。 { // 通过遍历生成树找出关节点。 cq.push_back( n ) ; int i ; deque < int > :: iterator j ; for ( i=0 ; i<citynum ; i++ ) if ( form[n][i] ) { form[n][i]=form[i][n]=false ; j=find(cq.begin(),cq.end(),i) ; if ( j!=cq.end() ) { while (++j,j!=cq.end()-1) if ( vp[*j] ) vp[*j]-- ; } else { vp[n]++ ; roam( i ) ; } } cq.pop_back() ; } void main() // 主函数负责数据输入，结果记录和输出工作。 { int connect ; int i ; string e , f ; vector < string > :: iterator ei , fi ; cout << "Input Please ..." << endl ; // 数据输入和数据格式检查 while ( cin >> citynum , citynum ) { citylist.assign(citynum,string("")) ; form.assign(citynum,vector < bool > (citynum,false)) ; vp.assign(citynum,0) ; vp[0]=-1 ; for ( i=0 ; i<citynum ; i++ ) { do { cin >> e ; if (find(citylist.begin(),citylist.end(),e)!=citylist.end()) cout << "Repeated Input !\nPass that ! Go on please ." << endl ; else break ; }while(1) ; citylist[i]=e ; } cin >> connect ; while ( connect-- ) { bool b=true ; do { cin >> e >> f ; ei=find(citylist.begin(),citylist.end(),e) ; fi=find(citylist.begin(),citylist.end(),f) ; if ( ei==citylist.end() || fi==citylist.end() ) cerr << "Can\'t find city\'s name in former name citylist !\nPass that ! Go on please ." << endl ; else if ( ei==fi ) cerr << "Two cities name can\'t be the same !\nPass that ! Go on please ." << endl ; else if ( form[ei-citylist.begin()][fi-citylist.begin()] ) cerr << "Repeated Input !\nPass that ! Go on please ." << endl ; else b=false ; } while(b) ; form[ei-citylist.begin()][fi-citylist.begin()]=form[fi-citylist.begin()][ei-citylist.begin()]=true ; } roam(0) ; // 调用 roam() 遍历生成树，产生结果。 result.push_back(vector < string > ()) ; for ( i=0 ; i<citynum ; i++ ) if (vp[i]>0) result[result.size()-1].push_back(citylist[i]) ; } cout << "Output Here Goes ..." << endl ; // 结果数据输出 int j ; for ( i=0 ; i<result.size() ; i++ ) { cout << "City map #" << i+1 << ": " << result[i].size() << " camera(s) found" << endl ; for ( j=0 ; j<result[i].size() ; j++ ) cout << result[i][j] << endl ; cout << endl ; } }

A5.

/************************************************************************/ /* created: 25/3/2004 12:21 */ /* platform: Microsoft Visual C++ v6.0 */ /* filename: Algorithm_A5 */ /* author: SunDrop */ /************************************************************************/ #pragma warning(disable:4786) // VC 版 STL 的一个 bug 。 #include <iostream> #include <string> #include <vector> #include <map> using namespace std; map < string , int > mEqp ; // 设备名称（未去"["和"]",没有必要）和设备号的 map 。 vector < vector < pair < int,int > > > vOFlow ; // 各组测试计划的电量溢出时刻表（溢出时刻和最大需求用电值）。 vector < int > vMax ; // 各组测试计划的最大用电量。 void main() // 主函数负责数据输入，结果记录和输出工作。 { cout << "Input Please ..." << endl ; // 数据输入，在 VC 下联输两个"Ctrl+Z , Enter"作为结束。 // 这可能是 VC 的 istream 类不合标准，因为在 DEV_C++ 中只用一个。 int num ; while ( true ) { cin >> num ; if ( num<=50000 ) break ; else cerr << "Input illegal ( too many equipments ) !" << endl << "Pass that ! Go on please ..." << endl ; } string e ; int a , b , k , p ; while ( num-- ) { while ( true ) { cin >> e >> a ; if ( e[0]=='[' && e[e.size()-1]==']' && a<500 ) break ; else cerr << "Input illegal ( unformated string or excess power need ) !" << endl << "Pass that ! Go on please ..." << endl ; } mEqp.insert( pair < string , int > ( e,a ) ) ; } int sum , max ; int kk ; while ( cin >> k , ! cin.eof() ) { cin >> p ; if ( k<0 || k>=2500 || p<1 || p>=800000 ) { cerr << "Input illegal ( too many/little records or unbelievable power supply ) !" << endl << "Pass that ! Go on please ..." << endl ; continue ; } kk = k ; map < int , int > mPower ; while ( k-- ) { while ( true ) { cin >> e >> a >> b ; if ( mEqp.find(e)==mEqp.end() || a<0 || b<0 || a>32768 || b>32768 ) { cerr << "Input illegal ( cannot find equipment or it runs at spear time ) !" << endl << "Pass that ! Go on please ..." << endl ; continue ; } else { mPower.insert( pair < int , int > ( a,+mEqp[e] ) ) ; mPower.insert( pair < int , int > ( b,-mEqp[e] ) ) ; break ; } } } vOFlow.push_back( vector < pair < int,int > > ( 0 ) ) ; sum=0 ; max=0 ; // 遍历各个关键时间点计算出用电量超标时刻，并存储结果。 if ( kk!=0 ) { for ( map < int , int > :: iterator i = mPower.begin () ; i!=mPower.end () ; i++ ) { sum+=i->second ; if ( sum>p ) (vOFlow.end()-1)->push_back(pair < int,int > (i->first,sum)) ; if ( sum>max ) max=sum ; } } vMax.push_back(max) ; } int i , j ; // 结果数据输出 for ( i=0 ; i<vMax.size() ; i++ ) if ( vOFlow[i].size() ) { cout << "The power will be out at time " ; for ( j=0 ; j<vOFlow[i].size()-1 ; j++ ) cout << vOFlow[i][j].first << "," ; cout << vOFlow[i][j].first << " because the power is " ; for ( j=0 ; j<vOFlow[i].size()-1 ; j++ ) cout << vOFlow[i][j].second << "," ; cout << vOFlow[i][j].second << " Watts and overloaded." << endl ; } else cout << "The maximum power needed is " << vMax[i] << " Watts." << endl ; }