PAT甲级C++总结（一）

1.min和max：返回a和b的最小值或最大值，有三个参数，前两个必需，为比较的参数，第三个为比较的方法，使用时需要加上头文件algorithm

2.C/C++，用0x3f3f3f3f表示无穷大，0xc0c0c0c0表示无穷小

3.dijk最短路径算法：(懒得解释，直接上代码）

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=100,INF=0x3f3f3f3f;
int m,n,c;//m为点数目,n为线的数目,c为起点
int map[N][N],vis[N],dis[N];//map为各点之间的权值数组,vis用于判断点是否用过,dis为起点到目标点的最短距离数组

void dijk(int c){
    dis[c]=0;//起点到起点的距离为0
    for(int i=0;i<m;i++){//循环n次每次加一个点，每次加入的点都是已更新完成的点
        int v=-1;
        for(int j=0;j<m;j++){
            //每次都遍历所有的点，从没加入图中的点中选一个到原点距离最小的点，加入图中
            if(!vis[j]&&(v==-1||dis[j]<dis[v])){
                v=j;
            }
        }
        vis[v]=1;
        for(int j=0;j<m;j++){//进行松弛操作
            dis[j]=min(dis[j],dis[v]+map[v][j]);
        }
    }
    return ;
}

int main(){
    cin>>m>>n>>c;
    memset(dis,INF,sizeof(dis));
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            if(i==j){
                map[i][j]=0;
            }else{
                map[i][j]=INF;
            }
        }
    }
    for(int i=0;i<n;i++){
        int a,b,d;
        cin>>a>>b>>d;
        map[a][b]=d;
        map[b][a]=d;
    }
    dijk(c);
    return 0;
}

4.如果需要调用函数的过程中对参数的改变保留下来，需要使用指针作为函数参数：

void doubleValue(int *val)
{
   *val *= 2;
}
int main(){
	int val;
	doubleValue(&val);
	return 0；
}	

如果直接使用函数参数，不会对参数本身造成影响

5.C语言判断溢出一般判断是否突然小于0即可，题目一些坑点在于整型变量本身并没有超过int范围，但是有一些运算中比如相加超过了int的范围，要注意

6.二分法查找，可以减少遍历的次数，每次比较开始和结束的中间值，通过对比中间值和查找值的大小来反复更改开始和结束值

long long int left=max+1,right=res1+1;
    while(left<=right){
        long long int mid=(left+right)/2;
        res2=toDecimal(a,mid);
        if(res2==res1){
            cout<<mid;
            flag=1;
            break;
        }else if(res2>res1||res2<0){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }

7.n个互相独立的连通分量组成一个连通图，只需要连n-1条线就可以

8.深度优先遍历dfs获取图的连通分量的数量：
用矩阵v[i][j]表示图的边，1为有，0为没有；用visit表示图的点是否已经经过

void dfs(int node){
	visit[node]=true;
	for(int i=0;i<n;i++){
	if(visit[n]==false&&v[node][i]=1){
	dfs(i);
	}
	}


int main(){
...
int cnt=0;//连通分量的数量
for(int i=0;i<n;i++）{
if(visit[i]==false){
dfs(i);//每次dfs运行到结束，将会将某个连通分量的所有点的visit数组值设置为true，即遍历完一个连通分量
cnt++;
}
...
return 0；

9.通过树的两种遍历获得另外的遍历，参考柳神的代码：
https://blog.csdn.net/liuchuo/article/details/52137796