算法自解

发表于 | 更新于 | 分类于

算法自解

最新版见：https://www.jianshu.com/p/252346e3497b

（更新中……）

努力让自己熟练编程，关键代码，然后快速入门。

数据结构等各种知识点屡看屡忘的我，为以后整理的笔记……

以《算法全解》《挑战程序设计竞赛 算法与数据结构》等为基础

常用的数据结构

stack 

1
2
3
4
5
入栈，如例：s.push(x);
出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s.top()
判断栈空，如例：s.empty()，当栈空时，返回true。
访问栈中的元素个数，如例：s.size()。

queue

1
2
3
4
5
6
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()

vector

1
2
3
4
5
vector< vector<int> > m;
vector<int> q;
q.push_back(3);
m.push_back(q);
m[0][0];

数组

1
C++不易获得数组长度，因此建议把数组长度传入方法里。

输入输出与具体方法

pintf函数是每次输出结果;

print,cout最好不要混用，print是即时刷新，等效cout<<flush；混用有时会表现顺序输出不同。

(%与/的应用)

日期差值

输入两个日期：YYYYMMDD格式，得到两个日期之间的差值。

对于一个整数，%100：得到整数后两位 /100得到整数除后两位的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。
//
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>

using namespace std;
bool issun(int year) {
	if ((year % 100 != 0 &&year % 4 == 0)||year%400==0) {//判断 闰年 的方法！！
		return true;
	}
	else{
		return false;
	}
}

int main()
{
	int a1, a2;
	int year1, year2, mon1, mon2, day1, day2;
	while(scanf("%d%d",&a1,&a2)!=EOF){
		//没有强调，需要保证前者早于后者。

		if (a1 > a2) {
			int tmp = a1;
			a1 = a2;
			a2 = tmp;
		}
		day1 = a1 % 100;//得到后两位
		a1 = a1 / 100;//得到除后两位的前面的数
		mon1 = a1 % 100;
		a1 = a1 / 100;
		year1 = a1 % 10000;//得到后四位
		day2 = a2 % 100;
		a2 = a2 / 100;
		mon2 = a2 % 100;
		a2 = a2 / 100;
		year2 = a2 % 10000;
		int days = 1;
		int mon[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
		int mons[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
		while (!(year1 == year2&&mon1 == mon2&&day1 == day2)) {
			day1++;

			if (issun(year1)) {
				if (day1 == mons[mon1] + 1) {
					day1 = 1;
					mon1++;
				}
			}
			else {
				if (day1 == mon[mon1] + 1) {
					day1 = 1;
					mon1++;
				}

			}
			if (mon1 == 13) {
				mon1 = 1;
				year1++;
			}
			days++;
		}
		printf("%d\n", days);

	}
    return 0;
}

进制转换

P进制转十进制y

$a_1a_2\dots a_n\to a_1P^{n-1}+\dots+a_2P^{1}+a_1$

1
2
3
4
5
6
int y=0,product=1;
while(x!=0){
    y=y+(x%10)*product;//y是结果，x%10为了得到个位数
    x=x/10;
    product=prodcut*P;//product的值会分别变成1，p,p^2,p^3,p^4…
}

十进制数y转换成Q进制数z

1
2
3
4
5
int z[40],num=0;
do{
    z[num++]=y%Q;//除基取余 得到最后一位数
    y=y/Q;
}while(y!=0);

这样z数组从高位z[num-1]到低位z[0]即为Q进制z,进制转换完成。

字符串

对于回文串的处理：1.根据对称性；2.利用for循环，从后向前遍历（逻辑性比较简单）

思路1.

假设字符串str的下标从0开始，由于“回文串”是正读和反读都一样的字符串，因此只需要遍历字符串的前一半（注意：不需要取到i==len/2)，如果出现字符str[i]不等于其对称位置str[len-1-i]，就说明这个字符串不是“回文串”；如果前一半的所有字符str[i]都等于对称位置 str[len-1-i],则说明这个字符串是回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <cstring>
const int maxn=256;
//判断字符串str是否是“回文串”
bool judge(char str[]){
    int len =strlen(str);//字符串长度
    for（int i=0;i<len/2;i++){//i枚举字符串的前一半
        if(str[i]!=str[len-1-i]){
            return false;
        }
        
    }
    return true;
}

全排列

（略）

二分查找

这里没有用递归（事实上是可以用递归的），这里是动态改变left和right的值。注意传入参数为A[]

思想，只要left木有大于right，就接着找，but根据大于小于动态变化mid为right或者left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
//A[]为严格递增序列，left为二分下界，right为二分上界，x为欲查询的数
//二分区间为左闭右闭的[left,right],传入的初值为[0,n-1]
int binarySearch(int A[],int left,int right,int x){
	int mid;//mid 为left和right中点
    while(left<=right){//不用递归，用while界定界限。
        mid=(left+right)/2;//取中点
        //有的时候会觉得(left+right)/2可能比较大，所以也可以用left+(right-left)/2
        if(A[mid]==x){
            return mid;
        }else if(A[mid]>x){
            //中间的数大于x
            right=mid-1;
        }else{//中间的数小于x
            left=mid+1;
            
        }
        
    }
    return -1;//查找失败

}
int main(){
    const int n=10;
    int A[n]={1,3,4,6,7,8,10,11,12,15};
    printf("%d%d\n",binarySearch(A,0,n-1,6),binarySearch(A,0,n-1,9));
    return 0;
}
输出3 -1；

排序

快排

注意，数组传 a[]或者*a

解析：1.递归程序。

结束标准：left>right

2.选定基准 a[left] 标兵 i和j

3.i和j比较换位。i和j相遇的条件：因为i和j分开运算，j先减，i后加，因为while小于的限制，i不可能超过j,

j停止的位置一定小于基准数（因为需要和i换）

i停止的位置可能大于基准数（和j换），可能=j（i,j条件的限制）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void quicksort(int a[],int left,int right){//x,起始点，y,长度 递归实现的快排，好像是这样的QAQ
	//注意对比和标程的区别
	int i,j,t,temp;
	if(left>=right)//传入left，right的要有越界提醒
		return;

	temp=a[left];//temp中存基准数
	i=left;
	j=right;
    //三个while，while中n次换位，while外一次换位
	while(i<j){//小于表明没有相遇 直到i和j相遇，i与j是一个数
		//顺序很重要，要先从右往左找
		while(a[j]>=temp&&i<j)//注意这里也要标明i<j，反复左移
			j--;//找到基准右侧比基准小的数
        
		//再从左往右找
		while(a[i]<=temp&&i<j)//注意这里一定是小于等于
			i++;//找到基准左侧比基准大的数
        
		//交换两个数在数组中的位置，
		if(i<j){
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}

	}
	//最终将基准数归位。即基准数为最左边那个数，先把它右边的数大于它小于它的排好，再将基准数归位。
	a[left]=a[i];
	a[i]=temp;

	quicksort(a,left,i-1);
	quicksort(a,i+1,right);
}

冒泡排序&选择排序

冒泡和选择的区别：

选择循环a[i]和a[j]

冒泡循环a[j]和a[j+1]，外面大层是i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void xuanze(int *a){//由大到小
//	int *b=a;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){//注意这里是i+1
			if(a[i]<a[j]){
				int tmp=a[j];
				a[j]=a[i];
				a[i]=tmp;
			}
		}
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

void maopao(int *a){
//	int *b=a;
	for(int i=0;i<n;i++){
		for(int j=0;j<n-i;j++){//注意这里是n-i
            //注意边界，第一次可能越界。思考怎么更改            
			if(a[j]<a[j+1]){//冒泡是j和j+1之间的关系
				int tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
		}
	}
	for(int i=0;i<n;i++){
		printf("%d",a[i]);
		printf("%s"," ");
	}
}

归并排序

先搞定递归的，日后再搞定非递归的。

（《算法笔记》）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int maxn=100;
void merge(int A[],int L1,int R1,int L2,int R2){
    //将数组A的L1,R1,L2,R2区间合并为有序区间。
    int i=L1,j=L2;
    int temp[maxn],index=0;//temp是合并数组的临时数组
    while(i<=R1&&j<=R2){//两个数组都没有过界
        if(A[i]<=A[j]){
            temp[index++]=A[i++];
        }else{
            temp[index++]=A[j++];
        }
    }
    while(i<=R1) temp[index++]=A[i++];//最后转移剩下的数组
    while(j<=R2) temp[index++]=A[j++];
    for(int i=0;i<index;i++){//因为是相邻的两个数组，更新开头的就可以
        A[L1+i]=temp[i];
    }
}
void mergesort(int A[],int left,int right){
    if(left<right){
        int mid=(left+right)/2;//这种递归都是不停地更新mid
        mergesort(A,left,mid);
        mergrsort(A,mid+1,right);//切分数组
        merge(A,left,mid,mid+1,right);//合并切分的数组
    }
}

堆

堆

完全二叉树，左孩子2i位，右孩子2i+1位

树中每个节点的值都不小于（或不大于）其左右孩子节点的值。

完全二叉树一般用数组存储

这里是较小堆，主要方法是向上或向下调整，都有low（向下调整的点），high（next）

增添是添到末尾，向上调整，注意边界条件，比上2时刻大于low；

删除是把末尾放在堆顶，向下调整，注意边界条件，*2小于high，需要比较左右孩子。

堆支持以下的基本操作:

  • build:建立一个空堆；
  • insert:向堆中插入一个新元素；【向上调整堆】
  • update：将新元素提升使其符合堆的性质；
  • get：获取当前堆顶元素的值；
  • delete：删除堆顶元素；【向下调整堆】
  • heapify：使删除堆顶元素的堆再次成为堆

标程（百练上对应题目AC代码）

PKU2017年夏令营机试题

定义一个数组，初始化为空。在数组上执行两种操作：

1、增添1个元素，把1个新的元素放入数组。

2、输出并删除数组中最小的数。

使用堆结构实现上述功能的高效算法。

输入

第一行输入一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入一个整数n，代表操作的次数。
每次操作首先输入一个整数type。
当type=1，增添操作，接着输入一个整数u，代表要插入的元素。
当type=2，输出删除操作，输出并删除数组中最小的元素。
1<=n<=100000。

输出

每次删除操作输出被删除的数字。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
2
5
1 1
1 2
1 3
2
2
4
1 5
1 1
1 7
2

样例输出

1
2
3
1
2
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<stdio.h>
#include<queue>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int MAX=100000;
int heap[100000+5];
void downjust(int low,int high){//low为欲调整节点，high为最后一个元素节点
    //自上向下调整
	int j=low;
	int k=2*low;//得到孩子
	while(k<=high){//我写的是！=
//		int tmp=heap[k];
        if(k+1<high&&heap[k+1]<heap[k]){//左右比较，取最小
            k=k+1;}
        if(heap[k]<heap[j]){
            swap(heap[k],heap[j]);//注意swap方法
            j=k;
            k=k*2;
        }else{//如果不小于，则后面的也都大于了，可以不用比较了，直接break
            break;
        }
	}

}

void upjust(int low,int high){
    //自下向上调整
	int k=high/2;
	int j=high;
	while(k>=low){
		if(heap[j]<heap[k]){
			swap(heap[j],heap[k]);
            j=k;
			k=k/2;

		}else{
			break;
		}

	}
}



int main(){
	int m;
	int high=0;//high初始化为0
	scanf("%d",&m);//输入m组
	for(int i=0;i<m;i++){
		int n;
		scanf("%d",&n);
		memset(heap,0,sizeof(heap));//清空每次操作后的堆
		high=0;
		for(int j=0;j<n;j++){
			int op,num;
			scanf("%d",&op);//得到操作
				if(op==1){//如果是增添
					scanf("%d",&num);
					heap[high]=num;//添到末尾
					upjust(0,high);//自下向上调整
					high++;
				}else{
					printf("%d",heap[0]);
					printf("%s","\n");
					heap[0]=heap[high-1];//得到最后一个数
					downjust(0,high-1);//自上向下调整
					high--;
				}
			

		}
	}

	return 0;
}

链表

二叉树

【有时间得写一写基本功能实现】

[C++实现（指针的用法和解析）和java实现]

基本结构（数组）

1.利用左孩子和右孩子分别是2i,和2i+1，轻松实现。

2.单纯构造node数组（from 《挑战程序设计语言》）

基本结构(链表)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct node{
    int data;
    node* lchild;//二叉树定义的每一个节点都是带指针的
    node* rchild;
}
//新建节点or插入节点，返回一个指针
node* newNode（int v){
    node* Node=new node();
    Node->data=v;
    Node->lchild=Node->rchild=NULL;
    return Node;
}
//二叉树的查找
void search(node* root,int x,int newdata){
    if(root==NULL){
        return;//空树
    }
    if(root->data==x){
        root->data=newdata;
    }
    search(root->lchild,x,newdata);//往左子树搜索x
    search（root->rchild,x,newdata);//往右子树搜索x
}
//二叉树的插入
void insert(node* &root,int x){
    if(root == NULL){
        root=newNode(x);
        return;
    }
    if(由二叉树的性质，x应该插在左子树){
        insert（root->lchild,x);
    }else{
        insert（root->rchild,x);
    }
}
//先序遍历
void preorder(node* root){
    if(root==NULL){
        return;
    }
   // printf中
    preorder(root->lchild);
    preorder(root->rchild);中左右
}

中序：左中右 后序：左右中

1
2
3
4
5
6
7
8
9
10
//层序
void LayerOrder（node* root）{ //BFS
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        if(now->lchild!=NULL) q.push(now->lchild);
        if(now->rchild!=NULL) q.push(now->rchild);
    }

遍历的非递归实现

思想：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> proorder(Node* root){
    //根左右
    vector<int> res;
    if(NULL==root){
        return res;
    }
    stack<Node*> s;
    s.put(root);
    while(!s.empty()){
        Node * node=s.top();
        s.pop();
        res.push_back(node_val);
        if(node->left){
            s.push(node->left);
        }
        if(node->right){
			s.push(node->right);
        }
    }
    reverse(res.begin(),res.end());//倒转方法
    return res;
}

（二叉搜索树 二叉树链表具体实现）一种链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
using namespace std;

//定义节点
typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    char data;
}BiTreeNode, *BiTree; 　　　 //*BiTree的意思是给 struct node*起了个别名，叫BiTree，故BiTree为指向节点的指针。


//按照前序顺序建立二叉树
void createBiTree(BiTree &T) //&的意思是传进来节点指针的引用，括号内等价于 BiTreeNode* &T,目的是让传递进来的指针发生改变
{               　　　　　　　　 
    char c;
    cin >> c;
    if('#' == c)             //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data=c;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}

//前序遍历二叉树并打印
void preTraverse(BiTree T)
{
    if(T)
    {
        cout<<T->data<<" ";
        preTraverse(T->lchild);
        preTraverse(T->rchild);
    }
}
//中序遍历二叉树并打印
void midTraverse(BiTree T)
{
    if(T)
    {
        midTraverse(T->lchild);
        cout<<T->data<<" ";
        midTraverse(T->rchild);
    }
}
//后续遍历二叉树并打印
void postTraverse(BiTree T)
{
    if(T)
    {
        postTraverse(T->lchild);
        postTraverse(T->rchild);
        cout<<T->data<<" ";
    }
}
int main()
{
    BiTree T;               //声明一个指向二叉树根节点的指针               
    createBiTree(T);
    cout<<"二叉树创建完成！"<<endl;
    cout<<"前序遍历二叉树："<<endl;
    preTraverse(T);
    cout<<endl;
    cout<<"中序遍历二叉树："<<endl;
    midTraverse(T);
    cout<<endl;
    cout<<"后序遍历二叉树："<<endl;
    postTraverse(T);
    return 0;
}

叶子节点路径

二叉树根到叶子节点每一条路径【求二叉树是否存在和值为N的路径】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
using namespace std;
struct node{
    int x;
    node* left=NULL;
    node* right=NULL;
}

node* newnode(int c){
    node* x0=new node();
    x0->x=c;
    return x0;
}
int count=0;
void sum(node* current,int result){
    //int data=-1;
    int data=current->x;
    newres=result*10+data;
    
    if(current->left!=NULL){
       
        sum(current->left,newres);
        
    }
    if(current->right!=NULL){
        sum(current->right,newres);      
        
    }
    if(current->rigth==NULL&&current->left==NULL){
         count+=newres;
        return;
    }
}

int main() {
    node *root =new node();
    root->x=1;
    
    
    //cout << "Hello World!" << endl;
}

dfs&bfs&dijiesiqula算法

快排 bfs dfs 图算法【算法课本、书】 dijiesiqula算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void dfs(G){
    for(G的每一个顶点u){
        if(vis[u]==false){//这个节点木有被访问过
            vis[u]=true;
            dfs(u);
           
        }
    }        
}
void bfs(){
    queue q;
    while(q非空){
        取出q的队首元素u进行访问
        for(从u出发可达的所有顶点v){
            if(v没被访问过)
                加入队列
        }
    }
}
//循环n次
void Dijkstra(G，d[],s){
    for(循环n次){
        u=使d[u]最小还未被访问的顶点；
        记u已被访问；
        for（从u出发能到达所有顶点v){
        	if(v未被访问&&以u为中介点能使s到顶点v距离更优){
                优化d[v]
            }
        }
    }
    
}

//值代表到原点的路径，开始别的均为极大，除了原点为0
//数组：点到原点的距离。二维矩阵：点与点之间的距离
void Dijkstra(int s){
    fill(d,d+MAXV,INF);//给节点赋予一个极大值
    d[s]=0;
    for(int i=0;i<n;i++){//注意这个for字，可能会被return终止
        int u=-1;MIN=INF;
        //找没有被访问过的点中，d(离源点距离)最小的，令u为那一个点
        //得到初始加入集合的点和它到集合的距离
        for(int j=0;j<n;j++){//这里也有个for，，用于求最小
            if(vis[j]==false&&d[j]<MIN){
				u=j;
                 MIN=d[j];
            }
        }
        if(u==-1)return;//没有找到（最后的终止条件）
        vis[u]=true;
        //对找到的那个点临接的每一个未被访问过的点，更新d值
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
            	d[v]=d[u]+G[u][v];
            }  
        }
    }
}

并查集（最小生成树）

【回顾博客上的那篇文章】https://www.jianshu.com/p/25b08412e313

G题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<stdio.h>
#include<queue>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int point[55];
int findfather(int a){//寻找祖先，开始的时候，祖先都是自己
    if(point[a]!=a){
        return findfather(point[a]);
    }else{
        return a;
    }
}

void unionab(int a,int b){//合并一个方向
    if(findfather(a)!=findfather(b)){
        point[a]=b;
    }
}

bool issame(int a,int b){//判断是否是一个祖先
    if(findfather(a)==findfather(b))
        return true;
    else
        return false;
}

int main(){

    int m;
    queue<int> answer;
    scanf("%d",&m);
    while(m!=0){
        int n;
        scanf("%d",&n);
        if(n==0){
            printf("%d",0);
            printf("%s","\n");
//          string s;
//          getline(cin,s);
            scanf("%d",&m);
            continue;

        }else{

            for(int i=0;i<55;i++){
                point[i]=i;
            }
            int line[n][3];
            for(int i=0;i<n;i++){
                for(int j=0;j<3;j++){
                    scanf("%d",&line[i][j]);
                }
            }
            int graph[m+1][m+1];
            int ans=0;
            int zuxian=-1;
            memset(graph,-1,sizeof(graph));
            for(int i=0;i<n;i++){
                int x=line[i][0],y=line[i][1],len=line[i][2];
                if(graph[x][y]==-1||graph[x][y]>len){
                    graph[x][y]=len;
                    graph[y][x]=len;
                }

            }
            int edge=0;
            for(int i=0;i<n;i++){
                int minx=0,miny=0;//
                int min=105;
                for(int i=1;i<=m;i++){
                    for(int j=i+1;j<=m;j++){

                        //每次找最小的，找到后可以赋一个较大值
                        if(graph[i][j]<min&&graph[i][j]!=-1){
                            minx=i;
                            miny=j;
                            min=graph[i][j];
                        }

                    }
                }

                if(!(minx==0&&miny==0)){
                        if(!issame(minx,miny)){//怎么保证单向呢
                            unionab(findfather(minx),findfather(miny));
                            ans+=min;
                            edge++;
                }


                graph[minx][miny]=105;
                graph[miny][minx]=105;
            }
            answer.push(ans);

        }




//      string s;
//      getline(cin,s);

        scanf("%d",&m);
    }
    while(!answer.empty()){
        printf("%d%s",answer.front(),"\n");
        answer.pop();
    }


//  int m;




    return 0;
}

动态规划

设计一个简单的任务队列, 要求分别在 1,3,4 秒后打印出 “1”, “2”, “3”

字典序

给你一个数字n(n < 1e9), 再给你一个数字k(k < n), 要求你找到1, 2, 3, … n按照字典序排序后, 第k大的数字 【看算法书】