引用:
|
作者: colinzhengj 自己编的,呵呵
城市间有公路相连。如果一个城市和K个城市相连,这个城市的“等级”为K。
小明幻想自己是执政者。他想要至少一个等级为A1的城市,至少一个等级为A2的城市……至少一个等级为An的城市。其他等级的城市都不要。
1<=Ai<=m。
请帮他设计这样一张地图并给出时间复杂度(关于m和n)
附加问题:设计一个算法使地图上的城市数最小。不是什么NP hard问题 |
最简单的一种实现:
C++ 代码:
#include <vector>
#include <iostream>
using namespace std;
struct Road{
int left;
int right;
Road(int l,int r):left(l),right(r){}
};
int main(){
const int N = 10; //number of cities
const int Level[N] = {1,2,2,3,4,2,4,5,3,2}; //0 < Level[i] < N
int city[N] = {0};
vector<Road> road;
for(int i = 0;i < N;++i){
for(int j = i + 1;j < N;++j){
if(city[i] == Level[i])
break;
else if(city[j] == Level[j])
continue;
else{
road.push_back(Road(i,j));
++city[i];
++city[j];
}
}
if(city[i] < Level[i]){
cout<<"Cannot solve the problem!\n";
break;
}
}
for(int i = 0;i < int(road.size());++i)
cout<<road[i].left<<"---"<<road[i].right<<endl;
return 0;
}