1:最短路
链式前向星；
点击查看代码
int head[maxn],to[maxn],nxt[maxn],val[maxn],tot;
void add(int x,int y,int z){
to[++tot]=y;
val[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
堆优化的dijkstra
点击查看代码
priority_queue<pair<int,int> >q;
void dijkstra(int s){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
dis[s]=maxn;
q.push(make_pair(maxn,s));
while(q.size()){
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i],z=val[i];
if(dis[y]<min(z,dis[x])){
dis[y]=min(z,dis[x]);
q.push(make_pair(dis[y],y));
}
}
}
}
2:搜索
模板
点击查看代码
int Search(int k) {
if (到目的地) 输出解;
else
for (i=1;i<=算符种数;i++)
if (满足条件) {
保存结果;
Search(k+1);
恢复：保存结果之前的状态{回溯一步}
}
}
3树
二叉树转普通树
点击查看代码
//结构图存图
struct tree
{
char data;
int prt,lch,rch;
};tree a[10000];
int main(){
cc();
cout<<endl;
return 0;
}
void cc(){
memset(a,0,sizeof(a));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].data;
int j,p;
cin>>j;
//第一个儿子变左儿子
if(j!=0){
a[i].lch=j;
a[j].prt=i;
}
//其余儿子为右儿子
p=j;
while(j!=0)
{
cin>>j;
if(j!=0){
a[p].rch=j;
a[j].prt=p;
p=j;
}
}
}
}
二叉树的遍历
点击查看代码
void qian(int x){
if(x!=0){
cout<<a[x].data;
qian(a[x].lch);
qian(a[x].rch);
}
}
void zhong(int x){
if(x!=0){
zhong(a[x].lch);
cout<<a[x].data;
zhong(a[x].rch);
}
}
void hou(int x){
if(x!=0){
hou(a[x].lch);
hou(a[x].rch);
cout<<a[x].data;
}
}
最优二叉树（哈夫曼树）
叶子之和为其根，n个叶子共组成2n-1的树
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct tree{//结构图存储
long long data;
long long lch,rch;
};
long long n,k;
tree a[200],b[200];
void init();
long long my_min();
long long my_max();
void min_huffman();
void max_huffman();
int main()
{
init();
max_huffman();
min_huffman();
cout<<a[2*n-1].data<<endl;
cout<<b[2*n-1].data<<endl;
return 0;
}
void init(){//输入
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].data;
b[i].data=a[i].data;
}
}
long long my_min(){//最小叶子节点
long long temp=0x7fffffffffffffff;
for(int i=1;i<=n;i++)
{
if(a[i].data<temp)
{
temp=a[i].data;
k=i;
}
}
a[k].data=0x7fffffffffffffff;
return temp;
}
long long my_max(){//最大叶子节点
long long temp=-1;
for(int i=1;i<=n;i++)
{
if(b[i].data>temp)
{
temp=b[i].data;
k=i;
}
}
b[k].data=-1;
return temp;
}
void min_huffman(){
for(int i=n+1;i<=2*n-1;i++)
{
a[i].lch=my_min();
a[i].rch=my_min();
a[i].data=a[i].lch*a[i].rch+1;
a[k].data=a[i].data;
}
}
void max_huffman(){
for(int i=n+1;i<=2*n-1;i++)
{
b[i].lch=my_max();
b[i].rch=my_max();
b[i].data=b[i].lch*b[i].rch+1;
b[k].data=b[i].data;
}
}
dp
个人理解：dp本质为暴力枚举 + 记忆化优化，以小边界带动整体，以点带面的逐级求值过程
个人dp方程理解：1：中间阶段转移情况联系实际 。2，点带面边界处理
背包板子
t[ ]:体积，v[ ]:价值
01背包
点击查看代码
for(int i=1;i<=m;i++)
for(int j=n;j>=t[i];j--){//一定要倒序，保证dis[j-t[i]]在本次循环未更新
dis[j]=max(dis[j],dis[j-t[i]]+v[i]);
}
完全背包
点击查看代码
for(int i=1;i<=m;i++)
for(int j=t[i];j<=n;j++){//这里为正序，因为物品有无数件
dis[j]=max(dis[j],dis[j-t[i]]+v[i]);
}
分组背包
点击查看代码
for(int i=1;i<=n;i++){
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
q[p]++; //p组数量++
t[p][q[p]]=x;
v[p][q[p]]=y; //转换01背包
}
for(int i=1;i<=m;i++)
for(int j=v;j>=1;j--){
dis[i][j]=dis[i-1][j];
for(int s=1;s<=q[i];s++){
if(j>=t[i][s])
dis[i][j]=max(dis[i][j],dis[i-1][j-t[i][s]]+v[i][s]);
}
}
背包变形
点击查看代码
//求叠加值种类/个数等问题，倒序遍历高度/重量等值，此时dis[i]表示i高度/重量可达到
for(int i=1;i<=n;i++)
for(int j=1;j<=p[i];j++)
for(int k=1000;k>=l[i];k--){
if(dis[k-l[i]]){
dis[k]=1;
}
}
线性dp
b[ ]:长度，a[ ],序列
最长上升序列
点击查看代码
for(i=1;i<=n;i++){
b[i]=1;
for(j=1;j<=i;j++){//j是否等于i根据题目分析
if(a[i]>a[j] && b[j]+1>b[i]){
b[i]=b[j]+1;
}
}
}
最长下降序列
点击查看代码
for(i=n;i>=1;i--){//倒着的最长上升序列即为最长下降序列
b[i]=1;
for(j=i+1;j<=n;j++){
if(a[i]>a[j] && b[j]+1>b[i]){
b[i]=b[j]+1;
}
}
}
区间dp
枚举长度，起点，断点
板子
点击查看代码
for(int l=2;l<=n;l++)
for(int i=1;i+l-1<=m;i++){
int j=i+l-1;
for(int k=i;k<j;k++){
a[i][j]=min(a[i][j],a[i][k]+a[k+1][j]+具体数值);
}
}
环拆链
二倍长度枚举起点和长度；
点击查看代码
for(int i=1;i<=n;i++){
scanf("%d",&ch[i],&f[i][i]);
f[i+n][i+n]=f[i][i];
}
for(int l=2;l<=n;l++)
for (int i=1;i+l-1<=2*n;i++){
int j=i+l-1;
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+具体数值);
}
}