PAT甲级学习笔记（二）
##续接上一篇PAT甲级DFS相关题目
1.1030 Travel Plan (30分)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 99999999;
const int MAXN = 510;
bool vis[MAXN] = {false};
vector<int> pre[MAXN];
vector<int> path, tempPath;
int d[MAXN], minCost = INF;
//定义图
int G[MAXN][MAXN], C[MAXN][MAXN];
int n, m, st, ed, c1, c2, dist, cost;
void Dijkstra(int s){
fill(d, d + MAXN, INF);//要初始化距离
d[s] = 0;//千万别忘了定义节点到自己的距离
for(int i = 0; i < n; i++){
int u = -1, MIN = INF;
for(int j = 0; j < n; j++){
if(vis[j] == false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;
vis[u] = true;
for(int v = 0; v < n; v++){
if(vis[v] == false && G[u][v] != INF){
if(d[v] > G[u][v] + d[u]){
d[v] = G[u][v] + d[u];
pre[v].clear();
pre[v].push_back(u);
}else if(d[v] == G[u][v] + d[u]){
// d[v] = G[u][v] + d[u];不用更新，距离相等更新啥
pre[v].push_back(u);
}
}
}
}
}
void DFS(int v){
if(v == st){
tempPath.push_back(v);
int tempCost = 0;
for(int i = tempPath.size() - 1; i > 0; i--){
int id = tempPath[i], idNext = tempPath[i-1];
tempCost += C[id][idNext];
}
if(tempCost < minCost){
minCost = tempCost;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i = 0; i < pre[v].size(); i++){
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main(){
scanf("%d%d%d%d", &n, &m, &st, &ed);
fill(G[0], G[0] + MAXN * MAXN, INF);//初始化图和花费
fill(C[0], C[0] + MAXN * MAXN, INF);
for(int i = 0; i < m; i++){
scanf("%d%d%d%d", &c1, &c2, &dist, &cost);
G[c1][c2] = G[c2][c1] = dist;
C[c1][c2] = C[c2][c1] = cost;
}
Dijkstra(st);
DFS(ed);
for(int i = path.size()-1; i >= 0; i--){
printf("%d ", path[i]);
}
printf("%d %d\n", d[ed], minCost);
return 0;
}
这是一道很经典的题目，要多看看，固定一下自己的书写方法。这道题需要注意1.一维数组和二维数组的初始化方式要记牢，否则会出现指针错误。2.Dijkstra时注意核心语句if的书写。3.输出路径的时候注意需要倒序输出，不要蒙，pre，tempPath，path不要写乱了。
2.1018 Public Bike Management (30分)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 99999999;
const int MAXN = 510;
int G[MAXN][MAXN], d[MAXN], w[MAXN];
bool vis[MAXN] = {false};
vector<int> path, tempPath;
vector<int> pre[MAXN];
int cmax, n, sp, m, at, bt, ct;
int minNeed = INF, minRemain = INF;
void Dijkstra(int s){
fill(d, d + MAXN, INF);
d[s] = 0;
for(int i = 0; i <= n; i++){
int u = -1, MIN = INF;
for(int j = 0; j <= n; j++){
if(vis[j] == false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;
vis[u] = true;
for(int v = 0; v <= n; v++){
if(vis[v] == false && G[u][v] != INF){
if(d[v] > d[u] + G[u][v]){
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[v] == d[u] + G[u][v]){
pre[v].push_back(u);
}
}
}
}
}
void DFS(int u){
if(u == 0){
tempPath.push_back(u);
int need = 0, remain = 0;
for(int i = tempPath.size() - 1; i >= 0; i--){
int id = tempPath[i];
if(w[id] > 0){
remain += w[id];
}else{
if(remain > abs(w[id])){
remain -= abs(w[id]);
}else{
need += abs(w[id]) - remain;
remain = 0;
}
}
// tempw += w[tempPath[i]];
}
if(need < minNeed){
minNeed = need;
minRemain = remain;
path = tempPath;
}else if(need == minNeed && remain < minRemain){
minRemain = remain;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(u);
for(int i = 0; i < pre[u].size(); i++){
DFS(pre[u][i]);
}
tempPath.pop_back();
}
int main(){
scanf("%d%d%d%d", &cmax, &n, &sp, &m);
fill(G[0], G[0] + MAXN*MAXN, INF);
// fill(w, w + MAXN, INF);
for(int i = 1; i <= n; i++){
scanf("%d", &w[i]);
w[i] = w[i] - cmax/2;
}
// w[0] = 0;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &at, &bt, &ct);
G[at][bt] = G[bt][at] = ct;
}
Dijkstra(0);
DFS(sp);
printf("%d ", minNeed);
for(int i = path.size()-1; i >= 0; i--){
printf("%d",path[i]);
if(i > 0) printf("->");
}
printf(" %d", minRemain);
return 0;
}
注意固定这种题目的写法都是Dijkstra + DFS,不管是不是最优子结构，都固定成这样的写法，这道题是点权，上一道题是边权，这两道题一定要记下来。
3.1087 All Roads Lead to Rome (30分)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int inf = 99999999;
const int maxn = 210;
map <string, int> m1;
map <int, string> m2;
int G[maxn][maxn], d[maxn], weight[maxn];
vector <int> path, temppath, pre[maxn];
bool vis[maxn] = {false};
int n, k, st;
int numpath = 0, maxw = 0;
double maxavg = 0;
void dijks(int s){
// cout <<"*";
fill(d, d + maxn, inf);
d[s] = 0;
for(int i = 0; i < n; i++){
int u = -1, min = inf;
for(int j = 0; j < n; j++){
if(vis[j] == false && d[j] < min ){
u = j;
min = d[j];
}
}
if(u == -1) return;
vis[u] = true;
for(int v = 0; v < n; v++){
if(vis[v] == false && G[u][v] != inf){
if(d[v] > d[u] + G[u][v]){
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[v] == d[u] + G[u][v]){
pre[v].push_back(u);
}
}
}
}
}
void dfs(int v){
if(v == st){
temppath.push_back(v);
numpath++;
int tempw = 0;
for(int i = temppath.size() - 2; i >= 0; i--){
int id = temppath[i];
tempw += weight[id];
// cout << "tempw = " << tempw << endl;
}
double tempavg = 1.0*tempw/(temppath.size()-1);
if(tempw > maxw){
// tempw = maxw;
maxw = tempw;
maxavg = tempavg;
path = temppath;
}else if(tempw == maxw && tempavg > maxavg){
maxavg = tempavg;
path = temppath;
}
temppath.pop_back();
return;
}
temppath.push_back(v);
for(int i = 0; i < pre[v].size(); i++){
dfs(pre[v][i]);
}
temppath.pop_back();
}
int main(){
string c1, c2, start;
cin >> n >> k >> start;
m1[start] = 0;
m2[0] = start;
for(int i = 1; i <= n-1; i++){
cin >> c1 >> weight[i];
m1[c1] = i;
m2[i] = c1;
}
fill(G[0], G[0] + maxn*maxn, inf);
for(int i = 0 ; i < k; i++){
int cost;
cin >> c1 >> c2 >> cost;
int city1 = m1[c1], city2 = m1[c2];
G[city1][city2] = G[city2][city1] = cost;
}
dijks(0);
int rom = m1["ROM"];
dfs(rom);
// cout << rom <<"*" << endl;
printf("%d %d %d %d\n",numpath, d[rom], maxw, (int)maxavg);
for(int i = path.size() - 1; i >= 0; i--){
cout << m2[path[i]];
if(i > 0) cout << "->";
// cout <<"%";
}
return 0;
}
4.1146 Topological Order (25分)
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, m, a, b, k, flag = 0, in[1010];
vector<int> v[1010];
scanf("%d %d",&n, &m);
for(int i = 0; i < m; i++){
scanf("%d %d", &a, &b);
v[a].push_back(b);
in[b]++;
}
scanf("%d", &k);
for(int i = 0; i < k; i++){
int judge = 1;
vector<int> tin(in, in+n+1);
//用in来初始化tin，起点表示从in[0]开始，一直到in[n],中间是两个指针迭代器
//只包括左边，不包括右边，所以应该是n+1而不是n
for(int j = 0; j < n; j++){
scanf("%d",&a);
if(tin[a] != 0) judge = 0;
// for(int it : v[a]) tin[it]--;//遍历v[a]的每一个数,相当于下面的语句
for(int l = 0; l < v[a].size(); l++){
tin[v[a][l]]--;
}
}
if(judge == 1) continue;
printf("%s%d", flag == 1 ? " " : "", i);
flag = 1;
}
return 0;
}
本题是一道关于拓扑排序的题，要注意如何设置临时的tin容器，并使用in数组来初始化，对于下面的遍历部分可以采用我自己的写法，更方便理解，不容易出错。
5.1020 Tree Traversals (25分)
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 50;
struct node{
int data;
node* lchild;
node* rchild;
};
int pre[maxn], in[maxn], post[maxn];
int n;
node* create(int postl, int postr, int inl, int inr){
if(postl > postr){
return NULL;
}
node* root = new node;
root->data = post[postr];//用来赋值的语句
int k;
for(k = inl; k <= inr; k++){
if(in[k] == post[postr]){
break;
}
}
int numleft = k - inl;
root->lchild = create(postl, postl+numleft-1, inl, k-1);
root->rchild = create(postl+numleft, postr-1, k+1,inr);
return root;
}
int num = 0;
void bfs(node* root){
queue<node*> q;
q.push(root);
while(!q.empty()){
node* now = q.front();
q.pop();
printf("%d", now->data);
num++;
if(num < n) printf(" ");
if(now->lchild != NULL) q.push(now->lchild);
if(now->rchild != NULL) q.push(now->rchild);
}
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &post[i]);
}
for(int i = 0; i < n; i++){
scanf("%d",&in[i]);
}
node* root = create(0, n-1, 0, n-1);
bfs(root);
return 0;
}
这是一道关于树给定前序遍历和中序遍历，输出层序遍历的题，简单的思路就是先建立二叉树，然后使用bfs搜索算法求解。当然也可以采用柳神的方法，代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int index, value;
};
bool cmp(node a, node b){
return a.index < b.index;
}
vector<int> post, in;
vector<node> ans;
void pre(int root, int start, int end, int index){
if(start > end) return;//表示递归边界
//下面两行代码表示寻找根节点在后序中的位置
int i = start;
while(i < end && in[i] != post[root]) i++;
//i,start, end都是中序遍历中的，root是后序遍历中的
ans.push_back({index, post[root]});
pre(root - (end - i) - 1, start, i - 1, 2*index + 1);
pre(root - 1, i + 1, end, 2 * index + 2);
}
int main(){
int n;
scanf("%d", &n);
post.resize(n);
in.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &post[i]);
for(int i = 0; i < n; i++) scanf("%d", &in[i]);
pre(n - 1, 0, n - 1, 0);
sort(ans.begin(), ans.end(), cmp);
for(int i = 0; i < ans.size(); i++){
if(i != 0) cout << " ";
cout << ans[i].value;
}
return 0;
}
6.1053 Path of Equal Weight (30分)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int w;
vector<int> child;
};
int target;
vector<int> path;
vector<node> v;
int cmp1(int a, int b){
return v[a].w > v[b].w;
}
void dfs(int index, int nodenum, int sum){
if(sum > target) return;
if(sum == target){
if(v[index].child.size() != 0) return;
for(int i = 0; i < nodenum; i++){
printf("%d%c", v[path[i]].w, i != nodenum - 1 ? ' ' : '\n');
}
return;
}
for(int i = 0; i < v[index].child.size(); i++){
int node1 = v[index].child[i];
path[nodenum] = node1;
dfs(node1, nodenum+1, sum + v[node1].w);
}
}
int main(){
int n, m, a, b;
scanf("%d %d %d", &n, &m, &target);
path.resize(n);
v.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &v[i].w);
for(int i = 0; i < m; i++){
scanf("%d %d", &a, &b);
v[a].child.resize(b);
for(int j = 0; j < b; j++){
scanf("%d",&v[a].child[j]);
}
sort(v[a].child.begin(), v[a].child.end(), cmp1);
}
dfs(0, 1, v[0].w);
return 0;
}
这道题给出了如何存储非二叉树，实际上和图的存储类似，甚至比图的存储简单些，这里面给出的非叶子结点只是为了遍历的时候，用作判断边界。注意初始化容器的时候，如果开始没有给出大小，后面输入的时候需要resize();
7.1086 Tree Traversals Again (25分)
这道题需要注意， 递归遍历搜索的时候，缺谁就使用哪种遍历，这道题使用的是后序遍历。注意根节点都是相对于前序遍历而言的，start， end，i都是相对中序遍历而言的。寻找i的时候，注意while中判断时i < end。起始条件是从n-1开始的，不是从n开始，需要注意，这道题也是一个模板，需要好好理解记忆；
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
stack <int> st;
int pre[35], in[35];
vector<int> ans;
void post(int root, int start, int end){
if(start > end) return;
int i = start;
while(i < end && in[i] != pre[root]) i++;
post(root + 1, start, i - 1);
post(root + i + 1 - start, i + 1, end);
ans.push_back(pre[root]);
// printf("%d ", pre[root]);
}
int main(){
int n;
cin >> n;
string s;
int a, i = 0, j = 0;
for(int k = 0; k < 2 * n; k++){
cin >> s;
if(s == "Push"){
cin >> a;
pre[i++] = a;
st.push(a);
}else{
in[j++] = st.top();
st.pop();
}
// cout << "popnum = " << popnum << endl;
}
post(0, 0, n - 1);
for(int k = 0; k < ans.size(); k++){
printf("%d", ans[k]);
if(k != ans.size() - 1) printf(" ");
}
return 0;
}
8.1102 Invert a Binary Tree (25分)
dfs一遍（就相当于中序遍历）将所有的点都标记上下标，和层数，然后按照排序后输出就是层序遍历，直接输出就是中序遍历，所有关于二叉树给定前序后序中序层序的写法都可这样做，如果不是二叉树怎么办呢？就只能建立树然后遍历了。注意树遍历的形式可能是数组，也可能是这道题这样的vector
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int id, l, r, index, level;
}a[100];//用来存储树
vector<node> v1;
void inorder(int root, int index, int level){
if(a[root].r != -1) inorder(a[root].r, index * 2 + 2, level + 1);
v1.push_back({root, 0, 0, index, level});
if(a[root].l != -1) inorder(a[root].l, index * 2 + 1, level + 1);
}
bool cmp1(node a, node b){
if(a.level != b.level) return a.level < b.level;
return a.index > b.index;
}
int main(){
int n, have[100] = {0}, root = 0;
//have数组是用来判断根节点是谁的，最开始假设为0
//根节点也先设置为0
cin >> n;
for(int i = 0; i < n; i++){
a[i].id = i;
string l, r;
cin >> l >> r;
if(l != "-"){
a[i].l = stoi(l);
have[stoi(l)] = 1;
}else{
a[i].l = -1;
}
if(r != "-"){
a[i].r = stoi(r);
have[stoi(r)] = 1;
}else{
a[i].r = -1;
}
}
while(have[root] == 1) root++;//所有点之中没有出现的就是根节点
//上面这种方法真的很巧妙
// cout << root << endl;
inorder(root, 0, 0);
vector<node> v2(v1);//这种使用v1来初始化v2的方式之前学过；
sort(v2.begin(), v2.end(), cmp1);
for(int i = 0; i < v2.size(); i++){
cout << v2[i].id;
if(i != v2.size() - 1) cout <<" ";
}
cout << endl;
for(int i = 0; i < v1.size(); i++){
cout << v1[i].id;
if(i != v1.size() - 1) cout <<" ";
}
return 0;
}
9.1079 Total Sales of Supply Chain (25分)
这道题注意dfs的时候尽量维护更少的变量，变量越多出错的概率越高。当对于vector容器想使用[i]这样的形式进行访问或输入的时候，需要确认大小，不然只能push_back。pow使用的时候level是int类型的也可以，因为，C/C++有约定，当一个“短”型值度赋给一个“长”型值时，自动将“短”型值提升为“长”型值。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n;
double p, r, sum = 0.0;
struct node{
int w;
vector<int> child;
};
vector<node> v;
void dfs(int node, int level){
if(v[node].child.size() == 0){
sum += pow(1+r, level) * v[node].w;
return;
}
// cout << "$$";
// if(num == n){
// printf("%.1f", sum);
// return;
// }
for(int i = 0; i < v[node].child.size(); i++){
int node1 = v[node].child[i];
dfs(node1, level + 1);
}
}
int main(){
scanf("%d %lf %lf", &n, &p, &r);
r /= 100;
v.resize(n);//必须要定义大小，不然输出不了
for(int i = 0; i < n; i++){
int t, c;
scanf("%d", &t);
// cout << "i = " << i << endl;
v[i].child.resize(t);
// cout << "&&";
if(t == 0) scanf("%d", &v[i].w);
else{
for(int j = 0; j < t; j++){
// scanf("%d", &c);
// v[i].child.push_back(c);
scanf("%d", &v[i].child[j]);
}
}
}
dfs(0, 0);
printf("%.1f", sum * p);
// cout << "*";
return 0;
}
10.1090 Highest Price in Supply Chain (25分)
这道题注意使用过node结点存储的时候一定是v[root].child.size()。一定要遍历到叶子结点再去处理相关的内容。注意输入错误，是i < n, 不是i< 9!!!
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct node{
// int isleaf = 1;
vector<int> child;
};
int n, root0;
double p, r;
vector<node> v;
int maxlevel = 0, sum = 0;
void dfs(int root, int level){
// cout << root << "&&" << endl;
// cout << "maxlevel = " << maxlevel << endl;
if(v[root].child.size() == 0){
if(level > maxlevel){
maxlevel = level;
sum = 0;
sum ++;
}else if(level == maxlevel){
sum++;
}
return;
}
for(int i = 0; i < v[root].child.size(); i++){
int node1 = v[root].child[i];
dfs(node1, level + 1);
}
}
int main(){
scanf("%d %lf %lf", &n, &p, &r);
v.resize(n);
r = r / 100;
// cout << r << "*" << endl;
for(int i = 0; i < n; i++){
int a;
scanf("%d", &a);
if(a != -1){
v[a].child.push_back(i);
// v[a].isleaf = 0;
}else{
root0 = i;
// v[a].isleaf = 0;
}
}
dfs(root0, 0);
printf("%.2f %d", p * pow(1 + r, maxlevel), sum);
return 0;
}
11.1106 Lowest Price in Supply Chain (25分)
这道题和前面的三道题类似，比较简单，注意读入树的时候不能使用scanf(“%d”,&v[i].child[j])这种形式，会出现错误，需要采用题目中的方式。设置最小高度的时候需要大一些，别少一个0就会出现错误。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n;
double p, r;
struct node{
vector<int> child;
};
vector<node> v;
int minlevel = 100005, minsum = 0;
void dfs(int index, int level){
if(v[index].child.size() == 0){
if(level < minlevel){
minlevel = level;
minsum = 1;
}else if(level == minlevel){
minsum++;
}
return;
}
for(int i = 0; i < v[index].child.size(); i++){
dfs(v[index].child[i], level+1);
}
}
int main(){
scanf("%d %lf %lf", &n, &p, &r);
v.resize(n);
for(int i = 0; i < n; i++){
int t;
scanf("%d", &t);
// cout << "t = " << t << endl;
for(int j = 0; j < t; j++){
int temp;
scanf("%d", &temp);
v[i].child.push_back(temp);
}
}
dfs(0, 0);
printf("%.4f %d", p * pow(1 + r / 100, minlevel), minsum);
return 0;
}
12.1138 Postorder Traversal (25分)
简单的一道前序中序转后序，注意这道题就是模板
#include <iostream>
#include <vector>
using namespace std;
int pre[50005], in[50005];
int f = 0;
void post(int root, int start, int end){
if(start > end) return;
int i = start;
while(i < end && pre[root] != in[i]) i++;
post(root + 1, start , i-1);
post(root + 1 + i - start,i+1, end);
if(f == 0){
printf("%d", pre[root]);
f = 1;
}
}
int main(){
int n, a;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &pre[i]);
}
for(int i = 0; i < n; i++){
scanf("%d", &in[i]);
// cout << "8";
}
post(0, 0, n-1);
// for(int i = 0; i < n; i++){
// printf("%d \n", ans[i]);
// }
// printf("%d",ans[0]);
}