poj1797(RE)

虽然这个代码RE了,但我在debug()了一下午的过程中,踩了一个又一个的坑,所以记录下来。

题目

大意

有 n 个城市,m 条道路,在每条道路上有一个承载量,现在要求从 1 到 n 城市最大承载量,而最大承载量就是从城市 1 到城市 n 所有通路上的最大承载量

思路

  • 以起点建立邻接表,用一个队列来存放所有起点为1的点;
  • 每次从队列中取出一个点,并把以取出点的终点为起点的点放入队列,继续往下找,直到遇到最终点(保存每次的最小承载量)或者没有下一个点;
  • 取出最小值中的最大值

代码

定义

struct Node{
int to;
int cost;
};
struct helpNode{
int from, to;
int cost;
};
bool cmp(helpNode a, helpNode b){
return a.from < b.from;
}
vector<vector<Node> > start;
vector<Node> save;
vector<Node> kong;
int T, N, M;

处理函数,找到最大承载量

int doit(){
queue<Node> Q;
for (int i = 0; i < start[1].size();i++){
Q.push(start[1][i]);
}
Node temp, next;
while(!Q.empty()){
temp = Q.front();
Q.pop();
if(temp.to==N){
save.push_back(temp);
}
int x = temp.to;
for (int i = 0; i < start[x].size();i++){
next = start[x][i];
if(temp.cost<next.cost){
next.cost = temp.cost;
}
Q.push(next);
}
}
int max = 0;
for (int i = 0; i < save.size();i++){
if(max<save[i].cost){
max = save[i].cost;
}
}
return max;
}

主函数(输入处理)

int main(){
cin >> T;
for (int i = 1; i < T + 1;i++){
cin >> N >> M;
save.clear();
start.clear();
kong.clear();
helpNode temp;
Node tt;
vector<helpNode> help;
int len = start.size();
for (int j = 0; j < M;j++){
cin >> temp.from >> temp.to >> temp.cost;
if(temp.from>temp.to){
swap(temp.from, temp.to);
}
//start[x].push_back(temp);
help.push_back(temp); //存储输入的所有点
}
sort(help.begin(), help.end(), cmp); //从小到大排序
temp = help[help.size() - 1];
help.push_back(temp); //增加最后一个元素 使最后两个一定相同
int number = 0;
for (int k = 0; k < help.size()-1;k++){
number = help[k].from;
tt.to = help[k].to;
tt.cost = help[k].cost;
if(help[k+1].from==help[k].from){
save.push_back(tt); //相同起点的放入一个数组中
}
else{
int n = number - start.size();
while(n!=0){
start.push_back(kong);
n--;
}
save.push_back(tt); //不同时,存入help[k];
start.push_back(save);
save.clear();
}
}
start.push_back(save); //存入最后一组起点相同de
save.clear();
int result = doit();
cout << "Scenario #" << i << ":" << endl;
cout << result << endl;
}
cout << endl;
return 0;
}

总结

vector

对vector更熟练的运用,尤其是二维动态的,两个维度都是动态增长,且满足图的需求,即需要让一部分一维数组元素为空。

初始化

  • 这是一个相当重要的过程,每次你需要用一个队列、数组或者邻接矩阵,都需要考虑一下是否需要初始化,怎样初始化。
  • 尤其需要注意每次循环完毕之后,当前的值是否被存起来了。