实例介绍
【实例简介】
【实例截图】
【实例截图】
【核心代码】
# 基础
递归斐波那契算法
```c
Fib1(int n)
{
if(n<1)
return -1;
if(n==1||n==2)
return 1;
return Fib1(n-1) Fib1(n-2);
}
```
迭代斐波那契算法
```c
Fib2(int n)
{
int i,s1,s2;
if(n<1)
return -1;
if(n==1||n==2)
return 1;
s1=1;
s2=1;
for(i=3;i<=n;i )
{
s2=s1 s2;
s1=s2-s1;
}
return s2;
}
```
# 贪心算法
基本流程:决定贪心策略->得到局部最优解->得到全局最优解
## 最优装载问题
```c
#include<iostream>
#include<algorithm>
const int N=10000;
using namespace std;
double w[N];
int main()
{
double c;
int n;
cout<<"请输入船的最大载重c和古董数量n"<<endl;
cin>>c>>n;
cout<<"请逐个输入古董的重量"<<endl;
for(int i=0;i<n;i )
cin>>w[i];
sort(w,w n);
double temp=0.0;
int ans=0;
for(i=0;i<n;i )
{
temp =w[i];
if(tmp<c)
ans ;
else
break;
}
cout<<"最多可装下";
cout<<ans<<endl;
return 0;
}
```
## 背包问题
```c
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10000;
struct three{
double w;
double v;
double p;
}s[N];
bool cmp(three a,three b)
{
return a.p>b.p;
}
int main()
{
int n;
double m;
cout<<"输入宝物的数量n和毛驴的承载能力m"<<endl;
cin>>n>>m;
cout<<"逐个输入宝物的重量w和价值v"<<endl;
for(int i=0;i<n;i )
{
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;
}
sort(s,s n,cmp);
double sum=0.0;
for(int i=0;i<n;i )
{
if(m>s[i].w)
{
m-=s[i].w;
sum =s[i].v;
}
else
{
sum =m*s[i].p;
break;
}
}
cout<<"可装载最大价值"<<sum<<endl;
return 0;
}
```
## 会议安排
```c
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Meet
{
int beg;
int end;
int num;
}meet[100];
class setMeet{
public:
void init();
void solve();
private:
int n,ans;
};
void setMeet::init()
{
int s,e;
cout<<"请输入会议总数:"<<endl;
cin>>n;
int i;
cout<<"输入会议的开始和结束时间:"<<endl;
for(i=0;i<n; i)
{
cin>>s>>e;
meet[i].beg=s;
meet[i].end=e;
meet[i].num=i 1;
}
}
bool cmp(Meet x,Meet y)
{
if(x.end==y.end)
return x.beg>y.beg;
return x.beg<y.beg;
}
void setMeet::solve()
{
sort(meet,meet n,cmp);
cout<<"排序完成的会议时间如下:"<<endl;
int i;
cout<<"会议编号"<<" 开始时间"<<" 结束时间"<<endl;
for(i=0;i<n;i )
{
cout<<" "<<meet[i].num<<"\t"<<meet[i].beg<<"\t"<<meet[i].end<<endl;
}
cout<<"选择会议的过程:"<<endl;
cout<<"选择第"<<meet[0].num<<"个会议"<<endl;
ans=1;
int last=meet[0].end;
for(i=1;i<n;i )
{
if(meet[i].beg>=last)
{
ans ;
last=meet[i].end;
cout<<"选择第"<<meet[i].num<<"个会议"<<endl;
}
}
cout<<"最多可安排"<<ans<<"个会议"<<endl;
}
int main()
{
setMeet sm;
sm.init();
sm.solve();
return 0;
}
```
## 最短路径
### Dijkstra算法
```c
#include<cstdio>
#include<iostream>
#include<cstring>
#include<windows.h>
#include<stack>
using namespace std;
const int N=100;
const int INF=1e7;
int map[N][N],dist[N],p[N],n,m;
bool flag[N];
void Dijkstra(int u)
{
for(int i=1;i<=n;i )
{
dist[i]=map[u][i];
flag[i]=false;
if(dist[i]==INF)
p[i]=-1;
else
p[i]=u;
}
dist[u]=0;
flag[u]=true;
for(int i=1;i<=n;i )
{
int temp=INF,t=u;
for(int j=i;j<=n;j )
if(!flag[j]&&dist[i]<temp)
{
t=j;
temp=dist[j];
}
if(t==u) return;
flag[t]=true;
for(int j=1;j<=n;j )
if(!flag[j]&&map[t][j]<INF)
if(dist[j]>(dist[t] map[t][j]))
{
dist[j]=dist[t] map[t][j];
p[j]=t;
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");
cout<<"输入城市的个数:"<<endl;
cin>>n;
cout<<"输入城市之间路线的个数:"<<endl;
cin>>m;
cout<<"输入城市之间的路线及距离:"<<endl;
for(int i=1;i<=n;i )
for(int j=1;j<=n;j )
map[i][j]=INF;
while(m--)
{
cin>>u>>v>>w;
map[u][v]=min(map[u][v],w);
}
cout<<"输入所在位置:"<<endl;
cin>>st;
Dijkstra(st);
cout<<"当前所在位置:"<<st<<endl;
for(int i=1;i<=n;i )
{
cout<<"当前:"<<st<<" - "<<"要去的位置:"<<i<<endl;
if(dist[i]==INF)
cout<<"sorry,no way"<<endl;
else
cout<<"最短距离为:"<<dist[i]<<endl;
}
return 0;
}
```
### 使用优先队列优化的Dijkstra算法
```c
#include<queue>
#include<iostream>
#include<ctring>
#include<windows.h>
using namespace std;
const int N=100;
const int INF=1e7;
int map[N][N],dist[N],n,m;
int flag[N];
struct Node{
int u,step;
Node(){};
Node(int a,int sp){
u=a;step=sp;
}
bool operator < (const Node& a)const{
return step>a.step;
}
}
void Dijkstra(int st)
{
priority_queue<Node> Q;
Q.push(Node(st,0));
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i )
dist[i]=INF;
dist[st]=0;
while(!Q.empty())
{
Node it=Q.top();
Q.pop();
int t=it.u;
if(flag[t])
continue;
flag[t]=1;
for(int i=1;i<=n;i )
{
if(!flag[i]&&map[t][i]<INF)
{
if(dist[i]>dist[t] map[t][i])
{
dist[i]=dist[t] map[t][i];
Q.push(Node(i,dist[i]));
}
}
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");
cout<<"输入城市的个数:"<<endl;
cin>>n;
cout<<"输入城市之间路线的个数:"<<endl;
cin>>m;
cout<<"输入城市之间的路线及距离:"<<endl;
for(int i=1;i<=n;i )
for(int j=1;j<=n;j )
map[i][j]=INF;
while(m--)
{
cin>>u>>v>>w;
map[u][v]=min(map[u][v],w);
}
cout<<"输入所在位置:"<<endl;
cin>>st;
Dijkstra(st);
cout<<"当前所在位置:"<<st<<endl;
for(int i=1;i<=n;i )
{
cout<<"当前:"<<st<<" - "<<"要去的位置:"<<i<<endl;
if(dist[i]==INF)
cout<<"sorry,no way"<<endl;
else
cout<<"最短距离为:"<<dist[i]<<endl;
}
return 0;
}
```
## 霍夫曼编码
```c
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 1000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
typedef struct //定义节点
{
double weight;
int parent;
int lchild;
int rchild;
char value;
}HNodeType;
typedef struct //定义编码类型
{
int bit[MAXBIT]; //存储01编码的数组
int start; //编码在数组中开始的位置,从最后往前减小
}HCodeType;
HNodeType HuffNode[MAXNODE]; //定义一个足够大的节点数组
HCodeType HuffCode[MAXLEAF];
void HuffmanTree (HNodeType HuffNode[MAXNODE],int n) //构造霍夫曼树
{
int i,j,x1,x2;
double m1,m2;
for(i=0;i<2*n-1;i ) //初始化节点数据
{
HuffNode[i].weight = 0;
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
}
for(i=0;i<n;i ) //输入节点数据
{
cout<<"please input the value and weight of leaf node "<<i 1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].weight;
}
for(i=0;i<n-1;i ) //循环合并n-1次
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n i;j ) //在已有的节点里找权重最小的且没有parent的节点
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} //最后m1,m2为最新权重节点的权重,x1,x2为其位置
HuffNode[x1].parent=n i;
HuffNode[x2].parent=n i;
HuffNode[n i].weight=m1 m2;
HuffNode[n i].lchild=x1;
HuffNode[n i].rchild=x2;
cout<<"x1.weight and x2.weight in round "<<i 1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl;
}
}
void HuffmanCode(HCodeType HuffCode[MAXLEAF],int n) //对生成的树进行编码
{
HCodeType cd; //临时结构体
int i,j,c,p;
for(i=0;i<n;i )
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent; //p为遍历过程中每个节点的parent值
while(p!=-1) //如果未到根节点
{
if(HuffNode[p].lchild==c) //为parent的左节点则在该处编码为0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--; //编码长度加1,start位置减1
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start 1;j<n;j )
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start; //将临时变量复制到编码结构体
}
}
int main()
{
int i,j,n;
cout<<""<<endl;
cin>>n;
HuffmanTree(HuffNode,n);
HuffmanCode(HuffCode,n);
for(i=0;i<n;i )
{
cout<<HuffNode[i].value<<" :Huffman code is: ";
for(j=HuffCode[i].start 1;j<n;j )
cout<<HuffCode[i].bit[j];
cout<<endl;
}
return 0;
}
```
## 最小生成树
子图:从原图中选中一些顶点和边组成的图.
生成子图:选中一些边和所有顶点组成的图.
生成树:正好是一棵树的生成子图.
最小生成树:权值之和最小的生成树.
### Prim算法
复杂度:O(n^2)
$$
$$
```c
#include<iostream>
using namespace std;
const int INF = 1e4;
const int N = 100;
bool s[N];
int closest[N]; //存储U集合中离U-V集合中最近的点
int lowcost[N]; //最近点间的距离
void Prim(int n,int u0,int c[N][N])
{
s[u0]=true; //初始值在U集合中
int i,j;
for(i=1;i<=n;i ) //初始化lowcost和closest数组
{
if(i!=u0)
{
lowcost[i]=c[u0][i];
closest[i]=u0;
s[i]=false;
}
else
lowcost[i]=0;
}
for(i=1;i<=n;i )
{
int temp = INF;
int t=u0;
for(j=1;j<=n;j ) //在集合U-V中找到离集合U中最近的点
{
if(!s[j]&&(lowcost[j]<temp))
{
t=j;
temp=lowcost[j];
}
}
if(t==u0)
break;
s[t]=true;
for(j=1;j<=n;j ) //更新closest和lowcost数组
{
if(!s[j]&&(c[t][j]<lowcost[j]))
{
lowcost[j]=c[t][j];
closest[j]=t;
}
}
}
}
int main()
{
int n,c[N][N],m,u,v,w;
int u0;
cout<<"请输入节点数n和边数m:"<<endl;
cin>>n>>m;
int sumcost=0;
for(int i=1;i<=n;i )
for(int j=1;j<=n;j )
c[i][j]=INF;
cout<<"输入节点数u,v和边值w:"<<endl;
for(int i=1;i<=m;i )
{
cin>>u>>v>>w;
c[u][v]=c[v][u]=w;
}
cout<<"输入任一节点u0:"<<endl;
cin>>u0;
Prim(n,u0,c);
cout<<"数组lowcost的内容为:"<<endl;
for(int i=1;i<=n;i )
{
cout<<lowcost[i]<<" ";
sumcost =lowcost[i];
}
cout<<endl;
cout<<"最小的花费是:"<<sumcost<<endl;
}
```
### Kruskal算法
复杂度:O(e*logn)
```c
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100;
int nodeset[N];
int n,m;
struct Edge{
int u;
int v;
int w;
}e[N*N]; //边集
bool cmp(Edge x,Edge y)
{
return x.w<y.w;
}
void Init(int n) //初始化点集,每个点为一个集合
{
for(int i =1;i<=n;i )
nodeset[i]=i;
}
int Merge(int a,int b) //避圈法,若线的两端在同一点集里,则会产生回路,应避免
{
int p=nodeset[a];
int q=nodeset[b];
if(p==q)
return 0;
for(int i=1;i<=n;i ) //将所有连接在一起的点构成同一点集
{
if(nodeset[i]==q)
nodeset[i]=p;
}
return 1;
}
int Kurskal(int n)
{
int ans=0;
for(int i=0;i<m;i )
if(Merge(e[i].u,e[i].v))
{
ans =e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main()
{
cout<<"输入节点数n和边数m:"<<endl;
cin>>n>>m;
Init(n);
cout<<"输入节点数u,v和边值w:"<<endl;
for(int i=1;i<=m;i )
cin>>e[i].u>>e[i].v>>e[i].w;
sort(e,e m,cmp);
int ans=Kurskal(n);
cout<<"最小花费是:"<<ans<<endl;
return 0;
}
```
### 并查集改进的Kruskal算法
复杂度:O(n^2)
$$
$$
```c
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100;
int father[N];
int n,m;
struct Edge{
int u;
int v;
int w;
}e[N*N];
bool cmp(Edge x,Edge y)
{
return x.w<y.w;
}
void Init(int n)
{
for(int i =1;i<=n;i )
father[i]=i;
}
int Find(int x)
{
if(x!=father[x])
father[x]=Find(father[x]);
return father[x];
}
int Merge(int a,int b)
{
int p = Find(a);
int q = Find(b);
if(p==q)
return 0;
if(p>q)
father[p]=q;
else
father[q]=p;
return 1;
}
int Kurskal(int n)
{
int ans=0;
for(int i=0;i<m;i )
if(Merge(e[i].u,e[i].v))
{
ans =e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main()
{
cout<<"输入节点数n和边数m:"<<endl;
cin>>n>>m;
Init(n);
cout<<"输入节点数u,v和边值w:"<<endl;
for(int i=1;i<=m;i )
cin>>e[i].u>>e[i].v>>e[i].w;
sort(e,e m,cmp);
int ans=Kurskal(n);
cout<<"最小花费是:"<<ans<<endl;
return 0;
}
```
# 分治法
## 二分搜索
### 循环搜索
```c
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int M=100;
int x,n,i;
int s[M];
int BinarySearch(int n,int s[],int x)
{
int low=0,high=n-1,middle;
while(low<=high)
{
middle=(low high)/2;
if(x==s[middle])
return middle;
else if(x<s[middle])
high=middle-1;
else
low=middle 1;
}
return -1;
}
int main()
{
cout<<"输入数列元素个数n:"<<endl;
while(cin>>n)
{
cout<<"依次输入数列元素:"<<endl;
for(i=0;i<n;i )
cin>>s[i];
sort(s,s n);
cout<<"排序后的数组:"<<endl;
for(i=0;i<n;i )
cout<<s[i]<<" ";
cout<<endl;
cout<<"输入要查找的元素:"<<endl;
cin>>x;
i=BinarySearch(n,s,x);
if(i==-1)
cout<<"没有查找到"<<endl;
else
cout<<"查找的元素在第"<<i 1<<"位"<<endl;
}
return 0;
}
```
### 递归搜索
```c
int recursionBS(int s[],int x,int low,int high)
{
if(low>high)
return -1;
int middle=(low high)/2;
if(x==s[middle])
return middle;
else if(s<s[middle])
return recursionBS(s,x,low,middle-1);
else
return recursionBS(s,x,middle 1,high);
}
```
## 合并排序
```c
#include<iostream>
#include<cstdio>
#include<cstdlib>
//#include<algorithm>
using namespace std;
void Merge(int A[],int low,int mid,int high)
{
int *B=new int[high-low 1];
int i=low,j=mid 1,k=0;
while(i<=mid&&j<=high)
{
if(A[i]<=A[j])
B[k ]=A[i ];
else
B[k ]=A[j ];
}
while(i<=mid)
B[k ]=A[i ];
while(j<=high)
B[k ]=A[j ];
for(i=low,k=0;i<=high;i )
A[i]=B[k ];
}
void MergeSort(int A[],int low,int high)
{
if(low<high)
{
int mid=(low high)/2;
MergeSort(A,low,mid);
MergeSort(A,mid 1,high);
Merge(A,low,mid,high);
}
}
int main()
{
int n,A[100];
cout<<"输入元素个数:"<<endl;
cin>>n;
cout<<"输入每个元素:"<<endl;
for(int i=0;i<n;i )
cin>>A[i];
MergeSort(A,0,n-1);
cout<<"合并排序结果为:"<<endl;
for(int i=0;i<n;i )
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
```
## 快速排序
#### 原始
```c
#include<iostream>
using namespace std;
int Partition(int r[],int low,int high)
{
int i=low,j=high,pivot=r[low];
while(i<j)
{
while(i<j&&r[j]>pivot) j--;
if(i<j)
swap(r[i ],r[j]);
while(i<j&&r[i]<=pivot) i ;
if(i<j)
swap(r[i],r[j--]);
}
return i;
}
void QuickSort(int r[],int low,int high)
{
int mid;
if(low<high)
{
mid=Partition(r,low,high);
QuickSort(r,low,mid-1);
QuickSort(r,mid 1,high);
}
}
int main()
{
int n,A[100];
cout<<"输入元素个数:"<<endl;
cin>>n;
cout<<"输入每个元素:"<<endl;
for(int i=0;i<n;i )
cin>>A[i];
QuickSort(A,0,n-1);
cout<<"快速排序结果为:"<<endl;
for(int i=0;i<n;i )
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
```
### 改进
可减少交换次数,提高效率
```c
int Partition2(int r[],int low,int high)
{
int i=low,j=high,pivot=r[low];
while(i<j)
{
while(i<j&&r[j]>pivot)
j--;
while(i<j&&r[i]<=pivot)
i ;
if(i<j)
swap(r[i ],r[j--]);
}
if(r[i]>pivot)
{
swap(r[i-1],r[low]);
return i-1;
}
swap(r[i],r[low]);
return i;
}
```
## 大整数乘法
```c
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
#define M 100
char sa[100],sb[100];
typedef struct _Node
{
int s[M];
int l;
int c;
}Node,*pNode;
void cp(pNode src,pNode des,int st,int l) //拆分函数,st为起点
{
int i,j;
for(i=st,j=0;i<st l;i ,j )
des->s[j]=src->s[i];
des->l=l;
des->c=st src->c;
}
void add(pNode pa,pNode pb,pNode ans)
{
int i,cc,k,palen,pblen,len;
int ta,tb;
pNode temp;
if((pa->c)<(pb->c)) //保证幂指数较大的为pa
{
temp=pa;
pa=pb;
pb=temp;
}
ans->c=pb->c; //结果的幂指数等于较小的幂指数
cc=0; //进位初始为0
palen=pa->l pa->c;
pblen=pb->l pb->c;
if(palen<pblen)
len=pblen;
else
len=palen; //总的长度为最长的那一个
k=pa->c-pb->c; //pa需要补充的0的个数
for(i=0;i<len-ans->c;i )
{
if(i<k) //pa的前k位都是补充的0
ta=0;
else
ta=pa->s[i-k];
if(i< pb->l)
tb=pb->s[i];
else //超过pb长度的位pb的值都是0
tb=0;
if(i>=pa->l k) //超过pa长度的位pa的值都是0
ta=0;
ans->s[i]=(ta tb cc)%10;
cc=(ta tb cc)/10;
}
if(cc)
ans->s[i ]=cc;
ans->l=i;
}
void mul(pNode pa,pNode pb,pNode ans)
{
int i,cc,w;
int ma=pa->l>>1,mb=pb->l>>1;
Node ah,al,bh,bl;
Node t1,t2,t3,t4,z;
pNode temp;
if(!ma||!mb) //当pa或pb有一个只有1位时开始乘法
{
if(!ma) //保证pa为较大值
{
temp=pa;
pa=pb;
pb=temp;
}
ans->c=pa->c pb->c; //结果的幂指数=两个乘数的幂指数之和
w=pb->s[0]; //pb只有1位,用常数表示
cc=0;
for(i=0;i<pa->l;i )
{
ans->s[i]=(w*pa->s[i] cc)%10;
cc=(w*pa->s[i] cc)/10;
}
if(cc)
ans->s[i ]=cc; //最后的进位填进数组最后
ans->l=i;
return;
}
cp(pa,&ah,ma,pa->l-ma);
cp(pa,&al,0,ma);
cp(pb,&bh,mb,pb->l-mb);
cp(pb,&bl,0,mb);
mul(&ah,&bh,&t1);
mul(&ah,&bl,&t2);
mul(&al,&bh,&t3);
mul(&al,&bl,&t4);
add(&t3,&t4,ans);
add(&t2,ans,&z);
add(&t1,&z,ans);
}
int main()
{
Node ans,a,b;
cout<<"输入大数1:"<<endl;
cin>>sa;
cout<<"输入大数2:"<<endl;
cin>>sb;
a.l=strlen(sa);
b.l=strlen(sb);
int z=0,i;
for(i=a.l-1;i>=0;i--) //把输入的字符转为数字并倒序存入数组
a.s[z ]=sa[i]-'0';
a.c=0;
z=0;
for(i=b.l-1;i>=0;i--)
b.s[z ]=sb[i]-'0';
b.c=0;
mul(&a,&b,&ans);
cout<<"结果为:"<<endl;
for(i=ans.l-1;i>=0;i--)
cout<<ans.s[i];
cout<<endl;
return 0;
}
```
## 分治算法复杂度求解
### 递归树求解法
$$
T(n)=
\begin{cases}
O(1), &\text{$n$=1}\\
aT(n/2) O(n),&\text{$n$>1}
\end{cases}
$$
求解过程:
$$
\begin{align}
T(n)&=aT(n/2) O(n)\\
&=a(aT(n/2^2) O(n/2)) O(n)\\
&=a^2T(n/2^2) aO(n/2) O(n)\\
&=a^2(aT(n/2^3) O(n/2^2)) aO(n/2) O(n)\\
&=a^3T(n/2^3) a^2O(n/2^2) aO(n/2) O(n)\\
&= ...\\
&=a^xT(n/2^x) a^xO(n/2^x) ... aO(n/2) O(n)\\
&=a^xT(n/2^x) (\frac{a^x}{2^x} \frac{a^{x-1}}{2^{x-1}} ... 1)O(n)
\end{align}
$$
令
$$
2^x=n
$$
则
$$
\begin{align}
T(n)&=\frac{a^x}{2^x}O(1) \frac{1-(\frac{a}{2})^x}{1-\frac{a}{2}}O(n)\\
&\approx\frac{a^x}{2^x}O(1) ((\frac{a}{2})^x-1)O(n)\\
&\approx(\frac{a}{2})^xO(n)\\
&= \frac{a^{logn}}{n}O(n)\\
&=a^{logn}O(1)\\
&=O(a^{logn})\\
&=O(n^{loga})
\end{align}
$$
### 大师解法
$$
T(n)=aT(n/b) f(n)
$$
设
$$
f(n)=O(n^d)
$$
解得:
$$
T(n)=
\begin{cases}
O(n^d)&\text{,公比$a/b^d<1$}\\
O(n^{\log_b{a}})&\text{,公比$a/b^d>1$}\\
O(n^d\log_b{n})&\text{,公比$a/b^d=1$}\\
\end{cases}
$$
# 动态规划
分治算法是自顶向下解决问题,动态规划是自底向上解决问题.
适合用动态规划解决的问题的特征:
- 最优子结构
- 子问题重叠(非必须)
## 最长公共子序列
```c
#include<iostream>
#include<cstring>
using namespace std;
#define N 100
int c[N][N],b[N][N];
/*
b[i][j]存储最优解的来源
b[i][j]=1:c[i][j]=c[i-1][j-1] 1
b[i][j]=2:c[i][j]=c[i][j-1]
b[i][j]=3:c[i][j]=c[i-1][j]
*/
char s1[N],s2[N];
int len1,len2;
void LCSL()
{
int i,j;
for(i=1;i<=len1;i )
for(j=1;j<=len2;j )
{
if(s1[i-1]==s2[j-1])
{
c[i][j]=c[i-1][j-1] 1;
b[i][j]=1;
}
else
{
if(c[i][j-1]>=c[i-1][j])
{
c[i][j]=c[i][j-1];
b[i][j]=2;
}
else
{
c[i][j]=c[i-1][j];
b[i][j]=3;
}
}
}
}
void Print(int i,int j)
{
if(i==0||j==0)
return;
if(b[i][j]==1) //即两个元素相同是打印
{
Print(i-1,j-1);
cout<<s1[i-1];
}
else if(b[i][j]==2)
Print(i,j-1);
else
Print(i-1,j);
}
int main()
{
int i,j;
cout<<"输入第一个序列:"<<endl;
cin>>s1;
cout<<"输入第二个序列:"<<endl;
cin>>s2;
len1=strlen(s1);
len2=strlen(s2);
for(i=0;i<=len1;i )
c[i][0]=0;
for(j=0;j<=len2;j )
c[0][j]=0;
LCSL();
cout<<"最长公共子序列的长度是:"<<c[len1][len2]<<endl;
cout<<"最长公共子序列是:";
Print(len1,len2);
return 0;
}
```
## 编辑距离
编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。
```c
#include<iostream>
#include<cstring>
using namespace std;
const int N=100;
char str1[N],str2[N];
int d[N][N];
int min(int a,int b)
{
return a<b?a:b;
}
int editdistance(char *str1,char *str2)
{
int len1=strlen(str1);
int len2=strlen(str2);
for(int i=0;i<=len1;i )
d[i][0]=i;
for(int j=0;j<=len2;j )
d[0][j]=j;
for(int i=1;i<=len1;i )
{
for(int j=1;j<=len2;j )
{
int diff;
if(str1[i-1]==str2[j-1])
diff=0;
else
diff=1;
int temp=min(d[i-1][j] 1,d[i][j-1] 1);
d[i][j]=min(temp,d[i-1][j-1] diff);
}
}
return d[len1][len2];
}
int main()
{
cout<<"输入str1："<<endl;
cin>>str1;
cout<<"输入str2："<<endl;
cin>>str2;
cout<<str1<<"和"<<str2<<"的编辑距离是："<<editdistance(str1,str2);
return 0;
}
```
## 游艇租赁
```c
#include<iostream>
using namespace std;
const int ms=100;
int r[ms][ms],m[ms][ms],s[ms][ms];
int n;
void rent()
{
int i,j,k,d;
for(d=3;d<=n;d )
{
for(i=1;j<=n-d 1;i )
{
j=i d-1;
for(k=i 1;k<j;k )
{
int temp;
temp=m[i][k] m[k][j];
if(temp<m[i][j])
{
m[i][j]=temp;
s[i][j]=k;
}
}
}
}
}
void print(int i,int j)
{
if(s[i][j]==0)
{
cout<<"--"<<j;
return;
}
print(i,s[i][j]);
print(s[i][j],j);
}
int main()
{
int i,j;
cout<<"输入站点个数：";
cin>>n;
cout<<"输入各站点间的租金：";
for(i=1;i<=n;i )
for(j=i 1;j<=n; j)
{
cin>>r[i][j];
m[i][j]=r[i][j];
}
rent();
cout<<"花费的最少租金为："<<m[1][n]<<endl;
cout<<"最少租金经过的站点为："<<1;
print(1,n);
return 0;
}
```
## 矩阵连乘
```c
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int msize=100;
int p[msize];
int m[msize][msize],s[msize][msize];
int n;
void matrixchain()
{
int i,j,r,k;
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
for(r=2;r<=n;r )
{
for(i=1;i<=n-r 1;i )
{
j=r i-1;
m[i][j]=m[i 1][j] p[i-1]*p[i]*p[j];
s[i][j]=i;
for(k=i 1;k<j;k )
{
int t=m[i][k] m[k 1][j] p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
void print(int i,int j)
{
if(i==j)
{
cout<<"A["<<i<<"]";
return;
}
cout<<"(";
print(i,s[i][j]);
print(s[i][j] 1,j);
cout<<")";
}
int main()
{
cout<<"输入矩阵个数n:";
cin>>n;
int i;
cout<<"逐个输入每个矩阵的行数和最后一个矩阵的列数：";
for(i=0;i<=n;i )
cin>>p[i];
matrixchain();
print(1,n);
cout<<endl;
cout<<"最小计算量的值为："<<m[1][n]<<endl;
}
```
## 最优三角剖分
```c
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=100;
int s[M][M];
int n;
double m[M][M],g[M][M];
void Convexpolygontriangulation()
{
for(int i=1;i<=n;i )
{
m[i][i]=0;
s[i][i]=0;
}
for(int d=2;d<=n;d )
for(int i=1;i<=n-d 1;i )
{
int j=i d-1;
m[i][j]=m[i 1][j] g[i-1][i] g[i][j] g[i-1][j];
s[i][j]=i;
for(int k=i 1;k<j;k )
{
double temp=m[i][k] m[k 1][j] g[i-1][k] g[k][j] g[i-1][j];
if(m[i][j]>temp)
{
m[i][j]=temp;
s[i][j]=k;
}
}
}
}
void print(int i,int j)
{
if(i==j)
return;
if(s[i][j]>i)
cout<<"{v"<<i-1<<"v"<<s[i][j]<<"}"<<endl;
if(j>s[i][j] 1)
cout<<"{v"<<s[i][j]<<"v"<<j<<"}"<<endl;
print(i,s[i][j]);
print(s[i][j] 1,j);
}
int main()
{
int i,j;
cout<<"输入顶点个数n：";
cin>>n;
n--;
cout<<"依次输入各顶点的连接权值：";
for(i=0;i<=n; i)
for(j=0;j<=n; j)
cin>>g[i][j];
Convexpolygontriangulation();
cout<<m[1][n]<<endl;
print(1,n);
return 0;
}
```
## 石子合并
```c
#include<iostream>
#include<string>
using namespace std;
const int INF=1<<10;
const int N=200;
int Min[N][N],Max[N][N];
int sum[N];//前n堆石子的数量
int a[N];//每堆石子的数量
int min_Circular,max_Circular;
void straight(int a[],int n)
{
for(int i=1;i<=n;i ) /初始化
Min[i][i]=0,Max[N][N]=0;
sum[0]=0;
for(int i=1;i<=n;i )
sum[i]=sum[i-1] a[i];
for(int v=2;v<=n;v ) //枚举合并的堆数规模
{
for(int i=1;i<=n-v 1;i )
{
int j=i v-1; //枚举终点j
Min[i][j]=INF; //初始化为最大值
Max[i][j]=-1; //初始化为-1
int tmp=sum[j]-sum[i-1];//记录i到j之间的石子数之和
for(int k=i;k<j;k ) //枚举中间分隔点
{
Min[i][j]=min(Min[i][j],Min[i][k] Min[k 1][j] tmp);
Max[i][j]=max(Max[i][j],Max[i][k] Max[k 1][j] tmp);
}
}
}
}
void Circular(int a[],int n)
{
for(int i=1;i<=n-1;i )
a[n i]=a[i];
n=2*n-1;
straight(a,n);
n=(n 1)/2;
min_Circular=Min[1][n];
max_Circular=Max[1][n];
for(int i=2;i<=n;i )
{
if(Min[i][n i-1]<min_Circular)
min_Circular=Min[i][n i-1];
if(Max[i][n i-1]>max_Circular)
max_Circular=Max[i][n i-1];
}
}
int main()
{
int n;
cout<<"输入石子堆数：";
cin>>n;
cout<<"依次输入各堆石子数：";
for(int i=1;i<=n;i )
cin>>a[i];
straight(a,n);
cout<<"直线型最小花费为："<<Min[1][n]<<endl;
cout<<"直线型最大花费为："<<Max[1][n]<<endl;
Circular(a,n);
cout<<"圆形最小花费为："<<min_Circular<<endl;
cout<<"圆形最大花费为："<<max_Circular<<endl;
return 0;
}
```
### 优化算法
```c
#include<iostream>
#include<string>
using namespace std;
const int INF=1<<10;
const int N=200;
int Min[N][N],Max[N][N],s[N][N];
int sum[N];
int a[N];
int min_Circular,max_Circular;
void get_Min(int n)
{
for(int v=2;v<=n;v )
{
for(int i=1;i<=n-v 1;i )
{
int j=i v-1;
int tmp=sum[j]-sum[i-1];
int il=s[i][j-1]>i?s[i][j-1]:i;
int jl=s[i 1][j]<j?s[i 1][j]:j;
Min[i][j]=Min[i][il] Min[il 1][j];
s[i][j]=il;
for(int k=il 1;k<=jl;k )
if(Min[i][k] Min[k 1][j]<Min[i][j])
{
Min[i][j]=Min[i][k] Min[k 1][j];
s[i][j]=k;
}
Min[i][j] =tmp;
}
}
}
void get_Max(int n)
{
for(int v=2;v<=n;v )
{
for(int i=1;i<=n-v 1;i )
{
int j=i v-1;
Max[i][j]=-1;
int tmp=sum[j]-sum[i-1];
if(Max[i 1][j]>Max[i][j-1])
Max[i][j]=Max[i 1][j] tmp;
else
Max[i][j]=Max[i][j-1] tmp;
}
}
}
void straight(int a[],int n)
{
for(int i=1;i<=n;i )
Min[i][i]=0,Max[i][i]=0,s[i][i]=0;
sum[0]=0;
for(int i=1;i<=n;i )
sum[i]=sum[i-1] a[i];
get_Min(n);
get_Max(n);
}
void Circular(int a[],int n)
{
for(int i=1;i<=n-1;i )
a[n i]=a[i];
n=2*n-1;
straight(a,n);
n=(n 1)/2;
min_Circular=Min[1][n];
max_Circular=Max[1][n];
for(int i=2;i<=n;i )
{
if(Min[i][n i-1]<min_Circular)
min_Circular=Min[i][n i-1];
if(Max[i][n i-1]>max_Circular)
max_Circular=Max[i][n i-1];
}
}
int main()
{
int n;
cout<<"输入石子堆数：";
cin>>n;
cout<<"依次输入各堆石子数：";
for(int i=1;i<=n;i )
cin>>a[i];
straight(a,n);
cout<<"直线型最小花费为："<<Min[1][n]<<endl;
cout<<"直线型最大花费为："<<Max[1][n]<<endl;
Circular(a,n);
cout<<"圆形最小花费为："<<min_Circular<<endl;
cout<<"圆形最大花费为："<<max_Circular<<endl;
return 0;
}
```
## 0-1背包问题
```c
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 1000
#define M 100
int c[M][maxn]; //c[i][j]表示前i个物品放入容量为j的购物车获得的最大价值
int w[M],v[M];
int x[M]; //x[i]表示第i个物品是否放入购物车
int main()
{
int i,j,n,W;
cout<<"输入物品个数n：";
cin>>n;
cout<<"输入购物车容量w：";
cin>>W;
cout<<"依次输入物品的重量和价值：";
for(i=1;i<=n;i )
cin>>w[i]>>v[i];
for(i=0;i<=n;i )
c[i][0]=0;
for(j=0;j<=W;j )
c[0][j]=0;
for(i=1;i<=n;i )
for(j=1;j<=W;j )
if(j<w[i]) //物品重量大于购物车容量之后不再放入
c[i][j]=c[i-1][j];
else
c[i][j]=max(c[i-1][j],c[i-1][j-w[i]] v[i]);
cout<<"可装最大价值为："<<c[n][W]<<endl;
j=W;
for(i=n;i>0;i--)
if(c[i][j]>c[i-1][j])
{
x[i]=1;
j-=w[i];
}
else
x[i]=0;
cout<<"装入购物车的物品为：";
for(i=1;i<=n;i )
if(x[i]==1)
cout<<i<<" ";
return 0;
}
```
## 快速定位-最优二叉搜索树
```c
#include<iostream>
#include<cmath>
using namespace std;
const int M=100;
double c[M][M],w[M][M],p[M],q[M];
int s[M][M];
int i,n,j,k;
void Opeimal_BST()
{
for(i=1;i<=n 1;i )
{
c[i][i-1]=0.0;
w[i][i-1]=q[i-1];
}
for(int t=1;t<=n;t ) //从下标为i开始的关键字到下标为j的关键字
for(i=1;i<=n-t 1;i )
{
j=i t-1;
w[i][j]=w[i][j-1] p[j] q[j];
c[i][j]=c[i][i-1] c[i 1][j];
s[i][j]=i; //初始化
//选择i 1到j之间的某个下标的关键字作为从i到j的根，如果组成的树的期望值当前最小，则k为从i到j的根节点
for(k=i 1;k<=j;k )
{
double temp=c[i][k-1] c[k 1][j];
if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6) //c 中浮点数不能直接比较
{
c[i][j]=temp;
s[i][j]=k; //k即为从下标i到j的根节点
}
}
c[i][j] =w[i][j];
}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
if(flag==0)
{
cout<<"S"<<s[i][j]<<" 是根"<<endl;
flag=1;
}
int k=s[i][j];
if(k-1<i) //如果左子树是叶子
cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
else //如果左子树不是叶子
{
cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
Construct_Optimal_BST(i,k-1,1);
}
if(k>=j) //如果右子树是叶子
{
cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
}
else //如果右子树不是叶子
{
cout<<"S"<<s[k 1][j]<<"is the right child of "<<"S"<<k<<endl;
Construct_Optimal_BST(k 1,j,1);
}
}
int main()
{
cout<<"输入关键字个数n:";
cin>>n;
cout<<"依次输入每个关键字的搜索概率：";
for(i=1;i<=n;i )
cin>>p[i];
cout<<"依次输入每个虚节点的搜索概率：";
for(i=0;i<=n;i )
cin>>q[i];
Opeimal_BST();
cout<<"最小搜索成本为："<<c[1][n]<<endl;
cout<<"最优二叉搜索树为：";
Construct_Optimal_BST(1,n,0);
return 0;
}
```
### 优化算法
~~~c
#include<iostream>
#include<cmath>
using namespace std;
const int M=100;
double c[M][M],w[M][M],p[M],q[M];
int s[M][M];
int i,n,j,k;
void Opeimal_BST()
{
for(i=1;i<=n 1;i )
{
c[i][i-1]=0.0;
w[i][i-1]=q[i-1];
}
for(int t=1;t<=n;t )
for(i=1;i<=n-t 1;i )
{
j=i t-1;
w[i][j]=w[i][j-1] p[j] q[j];
int il=s[i][j-1]>i?s[i][j-1]:i;
int jl=s[i 1][j]<j?s[i 1][j]:j;
c[i][j]=c[i][il-1] c[il 1][j];
s[i][j]=il;
for(k=il 1;k<=jl;k )
{
double temp=c[i][k-1] c[k 1][j];
if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)
{
c[i][j]=temp;
s[i][j]=k;
}
}
c[i][j] =w[i][j];
}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
if(flag==0)
{
cout<<"S"<<s[i][j]<<" 是根"<<endl;
flag=1;
}
int k=s[i][j];
if(k-1<i)
cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
else
{
cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
Construct_Optimal_BST(i,k-1,1);
}
if(k>=j)
{
cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
}
else
{
cout<<"S"<<s[k 1][j]<<"is the right child of "<<"S"<<k<<endl;
Construct_Optimal_BST(k 1,j,1);
}
}
int main()
{
cout<<"输入关键字个数n:";
cin>>n;
cout<<"依次输入每个关键字的搜索概率：";
for(i=1;i<=n;i )
cin>>p[i];
cout<<"依次输入每个虚节点的搜索概率：";
for(i=0;i<=n;i )
cin>>q[i];
Opeimal_BST();
cout<<"最小搜索成本为："<<c[1][n]<<endl;
cout<<"最优二叉搜索树为：";
Construct_Optimal_BST(1,n,0);
return 0;
}
~~~
## 算法技巧
最优子结构判定
- 作出一个选择
- 假定已经知道了那种选择是最优的
- 最优选择会产生哪些子问题
- 证明原问题的最优解包含子问题的最优解（通常使用反证法）
得到最优解递归式
- 分析原问题最优解和子问题最优解的关系
- 考查有多少种选择
- 得到最优解递归式
# 回溯法
回溯法是从初始状态出发，按照深度优先搜索的方式，根据产生子节点的条件约束，搜索问题的解。
隐约束（剪枝函数）
- 约束函数：能否得到问题的可行解的约束。
- 限界函数：能否代词最优解的约束。
## 0-1背包问题
```c
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
#define M 100
int i,j,n,W;
double w[M],v[M]; //每个物品的重量和价值
bool x[M]; //物品是否放入购物车的解
double cw,cp,bestp; //当前价值，当前重量和当前最优价值
bool bestx[M]; //当前最优解
double Bound(int i) //计算上界，即剩余物品的总价值
{
int rp=0;
while(i<=n)
{
rp =v[i];
i ;
}
return cp rp;
}
void Backtrack(int t) //用于搜索空间数，t表示当前扩展节点在第t层
{
if(t>n) //若已达到叶子节点
{
for(j=1;j<=n;j )
bestx[j]=x[j];
bestp=cp;
return ;
}
if(cw w[t]<=W) //满足限制条件搜索左子树
{
x[t]=1;
cw =w[t];
cp =v[t];
Backtrack(t 1);
cw-=w[t];
cp-=v[t];
}
if(Bound(t 1)>bestp) //满足限制条件搜索左子树
{
x[t]=0;
Backtrack(t 1);
}
}
void Knapsack(double W,int n)
{
cw=0;
cp=0;
bestp=0;
double sumw=0.0;
double sumv=0.0;
for(i=1;i<=n;i )
{
sumv =v[i];
sumw =w[i];
}
if(sumw<=W)
{
bestp=sumv;
cout<<"放入购物车的商品的最大价值为："<<bestp<<endl;
cout<<"将所有物品放入购物车。";
return;
}
Backtrack(1);
cout<<"放入购物车的商品的最大价值为："<<bestp<<endl;
cout<<"放入购物车的商品的标号为：";
for(i=1;i<=n;i )
{
if(bestx[i]==1)
cout<<i<<" ";
}
cout<<endl;
}
int main()
{
cout<<"请输入物品的个数：";
cin>>n;
cout<<"请输入购物车的容量：";
cin>>W;
cout<<"依次输入每个物品的重量和价值：";
for(i=1;i<=n;i )
cin>>w[i]>>v[i];
Knapsack(W,n);
return 0;
}
```
### 优化算法
```c
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define M 100
int i,j,n,W;
double w[M],v[M];
bool x[M];
double cw,cp,bestp;
bool bestx[M];
double Bound(int i)
{
double cleft=W-cw;
double brp=0.0;
while(i<=n&&w[i]<cleft)
{
cleft-=w[i];
brp =v[i];
i ;
}
if(i<=n)
{
brp =v[i]/w[i]*cleft;
}
return cp brp;
}
void Backtrack(int t)
{
if(t>n)
{
for(j=1;j<=n;j )
bestx[j]=x[j];
bestp=cp;
return ;
}
if(cw w[t]<=W)
{
x[t]=1;
cw =w[t];
cp =v[t];
Backtrack(t 1);
cw-=w[t];
cp-=v[t];
}
if(Bound(t 1)>bestp)
{
x[t]=0;
Backtrack(t 1);
}
}
struct Object
{
int id;
double d;
};
bool cmp(Object a1,Object a2)
{
return a1.d>a2.d;
}
void Knapsack(double W,int n)
{
cw=0;
cp=0;
bestp=0;
double sumw=0.0;
double sumv=0.0;
Object Q[n];
double a[n 1],b[n 1];
for(i=1;i<=n;i )
{
Q[i-1].id=i;
Q[i-1].d=1.0*v[i]/w[i];
sumv =v[i];
sumw =w[i];
}
if(sumw<=W)
{
bestp=sumv;
cout<<"放入购物车的商品的最大价值为："<<bestp<<endl;
cout<<"将所有物品放入购物车。";
return;
}
sort(Q,Q n,cmp);
for(i=1;i<=n;i )
{
a[i]=w[Q[i-1].id];
b[i]=v[Q[i-1].id];
}
for(i=1;i<=n;i )
{
w[i]=a[i];
v[i]=b[i];
}
Backtrack(1);
cout<<"放入购物车的商品的最大价值为："<<bestp<<endl;
cout<<"放入购物车的商品的标号为：";
for(i=1;i<=n;i )
{
if(bestx[i]==1)
cout<<Q[i-1].id<<" ";
}
cout<<endl;
}
int main()
{
cout<<"请输入物品的个数：";
cin>>n;
cout<<"请输入购物车的容量：";
cin>>W;
cout<<"依次输入每个物品的重量和价值：";
for(i=1;i<=n;i )
cin>>w[i]>>v[i];
Knapsack(W,n);
return 0;
}
```
## 最大团
团：当且仅当G‘不包含在G的更大的完全子图中，也就是说G’是G的极大完全子图时，G‘是G的团。
最大团：G的所有团中，含节点数最多的团。
```c
#include<iostream>
#include<string.h>
//#include<algorithm>
using namespace std;
#define M 100
int n,m,cn,bestn;
double a[M][M];
bool x[M];
bool bestx[M];
bool Place(int t)
{
bool ok=true;
for(int j=1;j<t;j )
{
if(x[j]&&a[t][j]==0)
{
ok=false;
break;
}
}
return ok;
}
void Backtrack(int t)
{
if(t>n) //到达叶节点
{
for(int i=1;i<=n;i )
bestx[i]=x[i];
bestn=cn;
return;
}
if(Place(t))//满足约束条件，进入左子树
{
x[t]=1;
cn ;
Backtrack(t 1);
cn--;
}
if(cn n-t>bestn)//满足限界条件，进入右子树
{
x[t]=0;
Backtrack(t 1);
}
}
int main()
{
int u,v;
cout<<"请输入部落的人数：";
cin>>n;
cout<<"请输入人与人的友好关系数：";
cin>>m;
memset(a,0,sizeof(a));//memset需要string.h头文件
cout<<"依次输入有友好关系的两个人：";
for(int i=1;i<=m;i )
{
cin>>u>>v;
a[u][v]=a[v][u]=1;
}
bestn=0;
cn=0;
Backtrack(1);
cout<<"最大人数为："<<bestn<<endl;
cout<<"国王护卫队成员为：";
for(int i=1;i<=n;i )
if(bestx[i])
cout<<i<<" ";
return 0;
}
```
## 地图着色
```c
#include<iostream>
#include<string.h>
//#include<algorithm>
using namespace std;
#define M 100
int n,m,edge,sum=0;
int a[M][M];
int x[M];
void Createa()
{
int u,v;
cout<<"请输入边数：";
cin>>edge;
memset(a,0,sizeof(a));
cout<<"依次输入有边连接的两个点：";
for(int i=1;i<=edge;i )
{
cin>>u>>v;
a[u][v]=a[v][u]=1;
}
}
bool Ok(int t)
{
for(int j=1;j<t;j )
{
if(a[t][j])
{
if(x[j]==x[t])
return false;
}
}
return true;
}
void Backtrack(int t)
{
if(t>n)
{
sum ;
cout<<"第"<<sum<<"种方案:";
for(int i=1;i<=n;i )
cout<<x[i]<<" ";
cout<<endl;
}
else
{
for(int i=1;i<=m;i )
{
x[t]=i;
if(Ok(t))
Backtrack(t 1);
}
}
}
int main()
{
cout<<"输入节点数：";
cin>>n;
cout<<"输入颜色数：";
cin>>m;
cout<<"输入无向图的邻接矩阵："<<endl;
Createa();
Backtrack(1);
return 0;
}
```
## n皇后问题
```c
#include<iostream>
#include<string.h>
#include<cmath>
//#include<algorithm>
using namespace std;
#define M 100
int n,countn;
int x[M];
bool Place(int t)
{
bool ok=true;
for(int j=1;j<t;j )
{
if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))
{
ok=false;
break;
}
}
return ok;
}
void Backtrack(int t)
{
if(t>n)
{
countn ;
for(int i=1;i<=n;i )
cout<<x[i]<<" ";
cout<<endl;
cout<<"-----------"<<endl;
}
else
{
for(int i=1;i<=n;i )
{
x[t]=i;
if(Place(t))
Backtrack(t 1);
}
}
}
int main()
{
cout<<"输入皇后个数：";
cin>>n;
countn=0;
Backtrack(1);
cout<<"答案的个数是："<<countn<<endl;
return 0;
}
```
## 最优加工顺序
```c
#include<iostream>
#include<string.h>
//#include<cmath>
#include<algorithm>
using namespace std;
#define M 100
const int INF=1000;
int n,bestf,f1,f2;
int x[M],bestx[M];
struct node
{
int x,y;
}T[M];
void Backtrack(int t)
{
if(t>n)
{
for(int i=1;i<=n;i ) //记录最优排列
bestx[i]=x[i];
bestf=f2;
return;
}
for(int i=t;i<=n;i ) //枚举
{
f1 =T[x[i]].x;
int temp=f2;
f2=max(f1,f2) T[x[i]].y;
if(f2<bestf) //限界条件
{
swap(x[t],x[i]); //交换
Backtrack(t 1); //继续深搜
swap(x[t],x[i]); //复位，反交换
}
f1-=T[x[i]].x;
f2=temp;
}
}
int main()
{
cout<<"输入机器零件个数：";
cin>>n;
cout<<"输入零件在两个机器上所需要的时间：";
for(int i=1;i<=n;i )
{
cin>>T[i].x>>T[i].y;
x[i]=i;
}
bestf=INF;
f1=f2=0;
memset(bestx,0,sizeof(bestx));
Backtrack(1);
cout<<"最优加工顺序是：";
for(int i=1;i<=n;i )
cout<<bestx[i]<<" ";
cout<<endl;
cout<<"最优加工时间为：";
cout<<bestf<<endl;
return 0;
}
```
### 优化算法
使用贝尔曼规则优化,复杂度可降至
$$
O(nlogn)
$$
```c
#include<iostream>
#include<string.h>
//#include<cmath>
#include<algorithm>
using namespace std;
#define M 100
int n;
struct node
{
int id;
int x,y;
}T[M];
bool cmp(node a,node b)
{
return min(b.x,a.y)>=min(b.y,a.x);
}
int main()
{
cout<<"输入机器零件个数：";
cin>>n;
cout<<"输入零件在两个机器上所需要的时间：";
for(int i=0;i<n;i )
{
cin>>T[i].x>>T[i].y;
T[i].id=i 1;
}
sort(T,T n,cmp);
int f1=0,f2=0;
for(int i=0;i<n;i )
{
f1 =T[i].x;
f2=max(f1,f2) T[i].y;
}
cout<<"最优加工顺序是：";
for(int i=0;i<n;i )
cout<<T[i].id<<" ";
cout<<endl;
cout<<"最优加工时间为：";
cout<<f2<<endl;
return 0;
}
```
## 最短旅行距离
```c
#include<iostream>
//#include<string.h>
//#include<cmath>
#include<algorithm>
using namespace std;
#define M 100
const int INF=1000;
int n,cl,bestl,x[M],g[M][M],bestx[M];
void Backtrack(int t)
{
if(t>n)
{ //最后一个城市与出发城市有边相连并且路径长度比当前最优值小，说明找到了一条更好的路径，记录相关信息
if(g[x[n]][1]!=INF&&(cl g[x[n]][1]<bestl))
{
for(int j=1;j<=n;j )
bestx[j]=x[j];
bestl=cl g[x[n]][1];
}
}
else
{
for(int j=t;j<=n;j )
{ //探索扩展节点的所有分支
//如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
if(g[x[t-1]][x[j]]!=INF&&(cl g[x[t-1]][x[j]]<bestl))
{
//保存第t个要去的城市编号到x[t]比赛，进入t 1层
swap(x[t],x[j]);
cl=cl g[x[t-1]][x[t]];
Backtrack(t 1);
cl-=g[x[t-1]][x[t]];
swap(x[t],x[j]);
}
}
}
}
void init()
{
bestl=INF;
cl=0;
for(int i=1;i<=n;i )
for(int j=i;j<=n;j )
g[i][j]=g[j][i]=INF;
for(int i=0;i<=n;i )
{
x[i]=i;
bestx[i]=0;
}
}
int main()
{
cout<<"输入地点个数：";
cin>>n;
init();
int m,u,v,dis;
cout<<"输入路线条数：";
cin>>m;
cout<<"输入每两个地点的距离：";
for(int i=1;i<=m;i )
{
cin>>u>>v>>dis;
g[u][v]=g[v][u]=dis;
}
Backtrack(2);
cout<<"最优旅行路线是：";
for(int i=1;i<=n;i )
cout<<bestx[i]<<" ";
cout<<endl;
cout<<"最短旅行距离为：";
cout<<bestl<<endl;
return 0;
}
```
## 算法技巧
定义合适的解空间
- 解的组织形式
- 显约束：对解分量的取值范围的限定
确定解空间的组织结构
搜索解空间
- 只求可行解，只需要约束函数
- 求最优解，需要约束函数和限界函数
# 分支限界法
## 0-1背包问题
```c
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=10;
bool bestx[N];
struct Node //定义节点
{
int cp,rp; //背包中的物品总价值和剩余物品总价值
int rw; //背包剩余容量
int id; //物品编号
bool x[N];//解向量
Node(){memset(x,0,sizeof(x));}//初始化
Node(int _cp,int _rp,int _rw,int _id)
{//构造函数
cp=_cp;
rp=_rp;
rw=_rw;
id=_id;
}
};
struct Goods
{
int value;
int weight;
}goods[N];
int bestp,W,n,sumw,sumv;
int bfs()//子集树的搜索
{
int t,tcp,trp,trw;
queue<Node> q; //创建普通队列
q.push(Node(0,sumv,W,1));//压入初始节点
while(!q.empty())
{
Node livenode,lchild,rchild;//3个节点
livenode=q.front();//队头元素为扩展节点
q.pop();//队头出队
t=livenode.id;
if(t>n||livenode.rw==0)
{
if(livenode.cp>=bestp)
{//更新最优值和最优解
for(int i=1;i<=n;i )
bestx[i]=livenode.x[i];
bestp=livenode.cp;
}
continue;
}
//判定当前节点是否满足限界条件，不满足则不扩展
if(livenode.cp livenode.rp<bestp)
continue;
//扩展左子树
tcp=livenode.cp;//当前购物车中价值
trp=livenode.rp-goods[t].value;//不管当前物品是否装入，剩余价值都会减少
trw=livenode.rw;//购物车剩余容量
if(trw>=goods[t].weight)//满足约束，放入购物车
{
lchild.rw=trw-goods[t].weight;
lchild.cp=tcp goods[t].value;
lchild=Node(lchild.cp,trp,lchild.rw,t 1);
for(int i=1;i<t;i )
lchild.x[i]=livenode.x[i];
lchild.x[t]=true;
if(lchild.cp>bestp)
bestp=lchild.cp;
q.push(lchild);//左孩子入队
}
//扩展右子树
if(tcp trp>=bestp)
{
rchild=Node(tcp,trp,trw,t 1);
for(int i=1;i<t;i )
rchild.x[i]=livenode.x[i];
rchild.x[t]=false;
q.push(rchild);//右孩子入队
}
}
return bestp;
}
int main()
{
cout<<"请输入物品个数：";
cin>>n;
cout<<"输入购物车容量：";
cin>>W;
cout<<"输入每个物品的重量和价值：";
for(int i=1;i<=n;i )
{
cin>>goods[i].weight>>goods[i].value;
sumv =goods[i].value;
sumw =goods[i].weight;
}
if(sumw<=W)
{
bestp=sumw;
cout<<"放入购物车的最大物品价值为："<<bestp<<endl;
cout<<"所有物品放入购物车。";
return 0;
}
bfs();
cout<<"放入购物车的最大物品价值为："<<bestp<<endl;
cout<<"放入购物车的物品序号为：";
for(int i=1;i<=n;i )
if(bestx[i])
cout<<i<<" ";
return 0;
}
```
### 优化-优先队列式分支限界法
```c
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=10;
bool bestx[N];
int w[N],v[N];//辅助数组，用于存储排序后的重量和价值
struct Node
{
int cp;
double up;//价值上界
int rw;
int id;
bool x[N];
Node(){memset(x,0,sizeof(x));}
Node(int _cp,double _up,int _rw,int _id)
{
cp=_cp;
up=_up;
rw=_rw;
id=_id;
}
};
struct Goods
{
int value;
int weight;
}goods[N];
struct Object
{ //辅助物品结构体，包含物品序号和单位重量价值，用于按单位重量价值排序
int id;
double d;//单位重量价值
}S[N];
bool cmp(Object a,Object b)
{
return a.d>b.d;
}
bool operator <(const Node &a,const Node &b)
{//定义队列的优先级，以up为优先级
return a.up<b.up;
}
int bestp,W,n,sumw,sumv;
double Bound(Node tnode)
{
double maxvalue=tnode.cp;
int t=tnode.id;
double left=tnode.rw;
while(t<=n&&w[t]<=left)
{
maxvalue =v[t];
left-=w[t];
}
if(t<=n)
maxvalue =1.0*v[t]/w[t]*left;
return maxvalue;
}
int proirbfs()
{
int t,tcp,tup,trw;
priority_queue<Node> q;
q.push(Node(0,sumv,W,1));
while(!q.empty())
{
Node livenode,lchild,rchild;
livenode=q.top();
q.pop();
t=livenode.id;
if(t>n||livenode.rw==0)
{
if(livenode.cp>=bestp)
{
for(int i=1;i<=n;i )
bestx[i]=livenode.x[i];
bestp=livenode.cp;
}
continue;
}
if(livenode.up<bestp)
continue;
tcp=livenode.cp;
trw=livenode.rw;
if(trw>=w[t])
{
lchild.rw=trw-w[t];
lchild.cp=tcp v[t];
lchild.id=t 1;
tup=Bound(lchild);
lchild=Node(lchild.cp,tup,lchild.rw,t 1);
for(int i=1;i<t;i )
lchild.x[i]=livenode.x[i];
lchild.x[t]=true;
if(lchild.cp>bestp)
bestp=lchild.cp;
q.push(lchild);
}
rchild.rw=trw;
rchild.cp=tcp;
rchild.id=t 1;
tup=Bound(rchild);
if(tup>=bestp)
{
rchild=Node(tcp,tup,trw,t 1);
for(int i=1;i<t;i )
rchild.x[i]=livenode.x[i];
rchild.x[t]=false;
q.push(rchild);
}
}
return bestp;
}
int main()
{
bestp=0;
sumv=sumw=0;
cout<<"请输入物品个数：";
cin>>n;
cout<<"输入购物车容量：";
cin>>W;
cout<<"输入每个物品的重量和价值：";
for(int i=1;i<=n;i )
{
cin>>goods[i].weight>>goods[i].value;
sumv =goods[i].value;
sumw =goods[i].weight;
S[i-1].id=i;
S[i-1].d=1.0*goods[i].value/goods[i].weight;
}
if(sumw<=W)
{
bestp=sumv;
cout<<"放入购物车的最大物品价值为："<<bestp<<endl;
cout<<"所有物品放入购物车。";
return 0;
}
sort(S,S n,cmp);
cout<<"排序后的物品价值和重量："<<endl;
for(int i=1;i<=n;i )
{
w[i]=goods[S[i-1].id].weight;//把排序后的数据传递给辅助数组
v[i]=goods[S[i-1].id].value;
cout<<w[i]<<" "<<v[i]<<endl;
}
proirbfs();
cout<<"放入购物车的最大物品价值为："<<bestp<<endl;
cout<<"放入购物车的物品序号为：";
for(int i=1;i<=n;i )
if(bestx[i])
cout<<S[i-1].id<<" ";
return 0;
}
```
## 最短旅行路径
```c
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=100;
const int INF=1000;
double g[N][N];
int bestx[N];
double bestl;
int n,m;
struct Node
{
double cl;
int id;
int x[N];
Node(){};
Node(double _cl,int _id)
{
cl=_cl;
id=_id;
}
};
//定义队列的优先级，以cl为优先级，cl值越小，越优先
bool operator <(const Node &a,const Node &b)
{
return a.cl>b.cl;
}
double Travelbfs()//优先队列式分支限界法搜索
{
int t;
Node livenode,newnode;
priority_queue <Node> q;//创建一个优先队列
newnode=Node(0,2); //创建根节点
for(int i=1;i<=n;i )
newnode.x[i]=i;//初始化根节点的解向量
q.push(newnode);//根节点加入优先队列
while(!q.empty())
{
livenode=q.top();
q.pop();
t=livenode.id;
if(t==n)
{
if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF)
if(livenode.cl g[livenode.x[n-1]][livenode.x[n]] g[livenode.x[n]][1]<bestl)
{
bestl=livenode.cl g[livenode.x[n-1]][livenode.x[n]] g[livenode.x[n]][1];
cout<<endl;
for(int i=1;i<=n;i )
bestx[i]=livenode.x[i];
}
continue;
}
if(livenode.cl>=bestl)
continue;
for(int j=t;j<=n;j )
{
if(g[livenode.x[t-1]][livenode.x[j]]!=INF)
{
double cl=livenode.cl g[livenode.x[t-1]][livenode.x[j]];
if(cl<bestl)
{
newnode=Node(cl,t 1);
for(int i=1;i<=n;i )
newnode.x[i]=livenode.x[i];
swap(newnode.x[t],newnode.x[j]);
q.push(newnode);
}
}
}
}
return bestl;
}
void init()
{
bestl=INF;
for(int i=0;i<=n;i )
bestx[i]=0;
for(int i=1;i<=n;i )
for(int j=i;j<=n;j )
g[i][j]=g[j][i]=INF;
}
void Print()
{
cout<<endl;
cout<<"最短路径：";
for(int i=1;i<=n;i )
cout<<bestx[i]<<"--->";
cout<<"1"<<endl;
cout<<"最短路径长度："<<bestl;
}
int main()
{
int u,v,w;
cout<<"输入景点数：";
cin>>n;
init();
cout<<"输入经典之间的连线数：";
cin>>m;
cout<<"依次输入两个景点间的距离：";
for(int i=1;i<=m;i )
{
cin>>u>>v>>w;
g[u][v]=g[v][u]=w;
}
Travelbfs();
Print();
return 0;
}
```
### 优化算法
```c
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=100;
const int INF=1000;
double g[N][N];
double minout[N];
double minsum;
int bestx[N];
double bestl;
int n,m;
struct Node
{
double cl,rl,zl;
//cl:当前已走过的路径长度
//rl：剩余路径长度的下界
//zl：当前路径长度的下界
int id;
int x[N];
Node(){};
Node(double _cl,double _rl,double _zl,int _id)
{
cl=_cl;
rl=_rl;
zl=_zl;
id=_id;
}
};
bool operator <(const Node &a,const Node &b)
{
return a.zl>b.zl;
}
bool Bound()
{
for(int i=1;i<=n;i )
{
double minl=INF;
for(int j=1;j<=n;j )
if(g[i][j]!=INF&&g[i][j]<minl)
minl=g[i][j];
if(minl==INF)
return false;
minout[i]=minl;
minsum =minl;
}
return true;
}
double Travelbfsopt()
{
if(!Bound())
return -1;
Node livenode,newnode;
priority_queue <Node> q;
newnode=Node(0,minsum,minsum,2);
for(int i=1;i<=n;i )
newnode.x[i]=i;
q.push(newnode);
while(!q.empty())
{
livenode=q.top();
q.pop();
int t=livenode.id;
if(t==n)
{
if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF)
if(livenode.cl g[livenode.x[n-1]][livenode.x[n]] g[livenode.x[n]][1]<bestl)
{
bestl=livenode.cl g[livenode.x[n-1]][livenode.x[n]] g[livenode.x[n]][1];
for(int i=1;i<=n;i )
bestx[i]=livenode.x[i];
}
continue;
}
if(livenode.cl>=bestl)
continue;
for(int j=t;j<=n;j )
{
if(g[livenode.x[t-1]][livenode.x[j]]!=INF)
{
double cl=livenode.cl g[livenode.x[t-1]][livenode.x[j]];
double rl=livenode.rl-minout[livenode.x[j]];
double zl=cl rl;
if(zl<bestl)
{
newnode=Node(cl,rl,zl,t 1);
for(int i=1;i<=n;i )
newnode.x[i]=livenode.x[i];
swap(newnode.x[t],newnode.x[j]);
q.push(newnode);
}
}
}
}
return bestl;
}
void init()
{
bestl=INF;
minsum=0;
for(int i=0;i<=n;i )
bestx[i]=0;
for(int i=1;i<=n;i )
for(int j=i;j<=n;j )
g[i][j]=g[j][i]=INF;
}
void Print()
{
cout<<endl;
cout<<"最短路径：";
for(int i=1;i<=n;i )
cout<<bestx[i]<<"--->";
cout<<"1"<<endl;
cout<<"最短路径长度："<<bestl;
}
int main()
{
int u,v,w;
cout<<"输入景点数：";
cin>>n;
init();
cout<<"输入经典之间的连线数：";
cin>>m;
cout<<"依次输入两个景点间的距离：";
for(int i=1;i<=m;i )
{
cin>>u>>v>>w;
g[u][v]=g[v][u]=w;
}
Travelbfsopt();
Print();
return 0;
}
```
## 最优工程布线
```c
#include<iostream>
#include<queue>
#include<iomanip>//io流控制头文件
using namespace std;
typedef struct
{
int x;
int y;
}Position;
int grid[100][100];//地图
bool findpath(Position s,Position e,Position *&path,int &PathLen)
{
if((s.x==e.x)&&(s.y==e.y))
{//判断是否起点就是终点
PathLen=0;
return true;
}
Position DIR[4],here,next;
DIR[0].x=0;//方向数组dir
DIR[0].y=1;
DIR[1].x=1;
DIR[1].y=0;
DIR[2].x=0;
DIR[2].y=-1;
DIR[3].x=-1;
DIR[3].y=0;
here=s;
grid[s.x][s.y]=0;//标记初始为0，未布线为-1，墙壁为-2
queue<Position> Q;
for(;;)
{
for(int i=0;i<4;i )
{
next.x=here.x DIR[i].x;
next.y=here.y DIR[i].y;
if(grid[next.x][next.y]==-1)
{
grid[next.x][next.y]=grid[here.x][here.y] 1;
Q.push(next);
}
if((next.x==e.x)&&(next.y==e.y))
break;
}
if((next.x==e.x)&&(next.y==e.y))
break;
if(Q.empty())
return false;
else
{
here=Q.front();
Q.pop();
}
}
PathLen=grid[e.x][e.y];
path=new Position[PathLen];
here =e;
for(int j=PathLen-1;j>=0;j--)
{
path[j]=here;
for(int i=0;i<4;i )
{
next.x=here.x DIR[i].x;
next.y=here.y DIR[i].y;
if(grid[next.x][next.y]==j)
break;
}
here=next;
}
return true;
}
void init(int m,int n)
{
for(int i=1;i<=m;i )
for(int j=1;j<=n;j )
grid[i][j]=-1;
for(int i=0;i<=n 1;i )
grid[0][i]=grid[m 1][i]=-2;
for(int i=0;i<=m 1;i )
grid[i][0]=grid[i][n 1]=-2;
}
int main()
{
Position a,b,*way;
int Len,m,n;
cout<<"输入方阵大小M，N："<<endl;
cin>>m>>n;
init(m,n);
while(!(m==0&&n==0))
{
cout<<"输入障碍物坐标x，y：（输入0 0结束）"<<endl;
cin>>m>>n;
grid[m][n]=-2;
}
cout<<"输入起点坐标：";
cin>>a.x>>a.y;
cout<<"输入终点坐标：";
cin>>b.x>>b.y;
if(findpath(a,b,way,Len))
{
cout<<"最短路径的长度为："<<Len<<endl;
cout<<"最佳路径坐标为："<<endl;
for(int i=0;i<Len;i )
cout<<setw(2)<<way[i].x<<setw(2)<<way[i].y<<endl;
}
else
cout<<"任务无法完成"<<endl;
}
```
# 线性规划网络流
线性规划是指从各种限制条件的组合中，选择处最为合理的计算方法，建立线性规划模型，从而求得最佳结果。
## 单纯形算法
基本变量：每个约束条件中的系数为正且只出现在一个约束条件中的变量。
非基本变量：除基本变量外的其它变量。
基本可行解：满足标准形式约束条件的可行解。
检验数：目标函数中非基本变量的系数。
线性规划基本定理：
1. 最优判别定理：若目标函数中关于非基本变量的所有系数小于等于0，则当前基本可行解就是最优解。
2. 无穷多最优解判别定理：若目标函数中关于非基本变量的所有检验数小于等于0，同时存在某个非基本变量的检验数等于0，则线性规划问题有无穷多个解。
3. 无界解定理：如果某个c_j检验数大于0，而c_j所对应的列向量的各分量a_1j,a_2j,...a_mj都小于等于0，则该线性规划问题有无界解。
单纯形表变换：
入基列=-原值/交叉位值（不包括交叉位）
离基行：原值/交叉位值（不包括交叉位）
交叉位：取原值倒数
C_0位：原值 同行入基列元素*同列离基行/交叉位值
一般位置元素=原值-同行入基列元素*同列离基行/交叉位值
## 工厂最大效益
```c
#include<iostream>
#include<math.h>
#include<iomanip>
#include<stdio.h>
using namespace std;
float kernal[100][100];//存储非单纯形表
char FJL[100]={};//非基本变量
char JL[100]={};//基本变量
int n,m,i,j;
void print()//输出单纯形表
{
cout<<endl;
cout<<"-------单纯形表如下：-------"<<endl;
cout<<" ";
cout<<setw(7)<<"b ";
for(i=0;i<=n;i )
cout<<setw(7)<<"x"<<FJL[i];
cout<<endl;
cout<<"c ";
for(i=0;i<=n;i )
{
if(i>=1)
cout<<"x"<<JL[i];
for(j=0;j<=m;j )
cout<<setw(7)<<kernal[i][j]<<" ";
cout<<endl;
}
}
void DCXA()
{
float max1,max2;//max1存放最大的检验数，max2存放最大正检验数对应的基本变量的最大系数
int e=-1;//记录入基列
int k=-1;//记录离基列
float min;
while(true)//循环迭代，直到找到问题的解或无解为止
{
max1=max2=0;
min=1000000;
for(j=1;j<=m;j )//找入基列，即最大正检验数对应的列
{
if(max1<kernal[0][j])
{
max1=kernal[0][j];
e=j;
}
}
if(max1<=0)//最大值<=0，即所有检验数<=0，满足获得最优解的条件
{
cout<<endl;
cout<<"获得最优解："<<kernal[0][0]<<endl;
print();
break;
}
for(i=1;i<=n;i )//找离基行，即常数列/入基列正比值最小对应的行
{
if(max2<kernal[i][e])
max2=kernal[i][e];
float temp=kernal[i][0]/kernal[i][e];
if(temp>0&&temp<min)//找离基变量
{
min=temp;
k=i;
}
}
cout<<"基列变量："<<"x"<<FJL[e]<<" ";
cout<<"离基变量："<<"x"<<JL[k]<<endl;
if(max2==0)
{
cout<<"解无界"<<endl;
break;
}
//变基变换
char temp=FJL[e];
FJL[e]=JL[k];
JL[k]=temp;
for(i=0;i<=n;i )//计算除入基列和出基行的所有位置的元素
{
if(i!=k)
{
for(j=0;j<=m;j )
{
if(j!=e)
{
if(i==0&&j==0)//计算特殊位c0，即目标函数的值
kernal[i][j]=kernal[i][j] kernal[i][e]*kernal[k][j]/kernal[k][e];
else//计算一般位置的值
kernal[i][j]=kernal[i][j]-kernal[i][e]*kernal[k][j]/kernal[k][e];
}
}
}
}
for(i=0;i<=n;i )//计算离基行的元素的值
{
if(i!=k)
kernal[i][e]=-kernal[i][e]/kernal[k][e];
}
for(j=0;j<=m;j )//计算入基列元素的值
{
if(j!=e)
kernal[k][j]=kernal[k][j]/kernal[k][e];
}
kernal[k][e]=1/kernal[k][e];//计算交叉位元素的值
print();
}
}
int main()
{
cout<<"输入非基本变量个数和非基本变量下标："<<endl;
cin>>m;
for(i=1;i<=m;i )
cin>>FJL[i];
cout<<"输入基本变量个数和基本变量下标："<<endl;
cin>>n;
for(i=1;i<=n;i )
cin>>JL[i];
cout<<"输入约束标准型初始单纯形表参数："<<endl;
for(i=0;i<=n;i )
{
for(j=0;j<=m;j )
cin>>kernal[i][j];
}
print();
DCXA();
return 0;
}
```
## 最大网络流
网络是一个有向带权图，包含一个源点和一个汇点，没有反平行边。
网络流：网络流即网络上的流，是定义在网络边集E上的一个非负函数flow={flow(u,v)}，flow(u,v)是边上的流量。
可行流：满足容量约束和流量守恒的流。
网络最大流：在满足容量约束和流量守恒的前提下，在网络流中找到一个净输出最大的网络流。
实流网络：只显示实际流量的网络。不显示容量。
残余网络：与网络边对应的同向边是可增量（即还可以增加多少流量），反向边是实际流量。
可增广路是残余网络中一条从源点到汇点的简单路径。
可增广量是指在可增广路p上每条边可以增加的流量最小值。
### 最短增广路算法（Edmonds-Karp算法）
```c
#include<iostream>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;
const int maxn=100;
const int INF=10000;
int g[maxn][maxn];//残余网络
int f[maxn][maxn];//实流网络
int pre[maxn];//前驱数组
bool vis[maxn];//访问数组
int n,m;
bool bfs(int s,int t)
{
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
queue<int>q;
vis[s]=true;
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=1;i<=n;i )//寻找可增广路
{
if(!vis[i]&&g[now][i]>0)//未被访问且有边相连
{
vis[i]=true;
pre[i]=now;
if(i==t)//找到一条可增广路
return true;
q.push(i);
}
}
}
return false;//找不到可增广路
}
int EK(int s,int t)
{
int v,w,d,maxflow;
maxflow=0;
while(bfs(s,t))//可以增广
{
v=t;
d=INF;
while(v!=s)//找可增量
{
w=pre[v];//记录v的前驱
if(d>g[w][v])
d=g[w][v];
v=w;
}
maxflow =d;
v=t;
while(v!=s)//沿可增广路增流
{
w=pre[v];
g[w][v]-=d;//残余网络中正向边减流
g[v][w] =d;//残余网络中反向边增流
if(f[v][w]>0)//实流网络中如果是反向边则减流，反之增流
f[v][w]-=d;
else
f[w][v] =d;
v=w;
}
}
return maxflow;
}
void print()//输出实流网络
{
cout<<endl;
cout<<"-------实流网络如下：-------"<<endl;
cout<<" ";
for(int i=1;i<=n;i )
{
cout<<"v"<<i;
for(int j=1;j<=n;j )
cout<<setw(7)<<f[i][j]<<" ";
cout<<endl;
}
}
int main()
{
int u,v,w;
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
cout<<"输入节点个数和边数："<<endl;
cin>>n>>m;
cout<<"输入两个节点u，v及边（u--v）的容量w："<<endl;
for(int i=1;i<=m;i )
{
cin>>u>>v>>w;
g[u][v] =w;
}
cout<<"网络的最大流值："<<EK(1,n)<<endl;
print();
return 0;
}
```
### 重贴标签算法ISAP
```c
#include<iostream>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=100;
const int M=10000;
const int INF=100000;
int top;
int h[N],pre[N],g[N];//h数组记录每个节点的高度，即到汇点的最短距离
//g数组记录距离为h[]的节点的个数
//pre数组记录当前节点的前驱边
struct Vertex//邻接表头节点
{
int first;
}V[N];
struct Edge//边结构体
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));//初始化邻接表头节点第一个邻接边为-1
top=0;//初始化边的下标为0
}
void add_edge(int u,int v,int c)//创建边
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;//链接到邻接表中
V[u].first=top ;
}
void add(int u,int v,int c)//添加两条边
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)//标高函数
{
queue <int>Q;//创建一个队列，用于广度优先搜索
memset(h,-1,sizeof(h));//初始化高度函数为-1
memset(g,0,sizeof(g));
h[t]=0;//初始化汇点的高度为0
Q.push(t);//入队
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{//读节点v的邻接边标号
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[ ]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)//搜索当前节点的邻接边
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{//沿有可增量和高度减1的方向搜索
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{//到达汇点，找到一条增广路径
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
//j为u的前驱边，即增广路上j为u的入边
E[j].flow =d;
//j边的流量 d
E[j^1].flow-=d;
//j的反向边的流量-d
u=E[j^1].v;
/*j^1表示j和1的与运算，因为创建边时是成对创建的，0号边的反向边是1号，二进制0和1的与运算正好是1号，即2号边的反向边是3号，二进制10和1的与运算正好是11，即3号，因此当前边号和1的与运算可以得到当前边的反向边*/
cout<<"--"<<u;//向前搜索
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break; //找到一条可行邻接边，退出for语句，继续向前走
}
}
if(i==-1)//当前节点的所有邻接边均搜索完毕，无法行进
{
if(--g[h[u]]==0)//如果该高度的节点只有1个，算法结束
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)//搜索u的所有邻接边
if(E[j].cap>E[j].flow)//有可增量
hmin=min(hmin,h[E[j].v]);//取所有邻接点高度的最小值
h[u]=hmin 1;//重新标高：所有邻接点高度的最小值 1
cout<<"重贴标签后高度"<<endl;
cout<<"h[ ]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];//重新标高后该高度的节点数 1
if(u!=s)//如果当前结点不是源点
u=E[pre[u]^1].v;//向前退回一步，重新搜索增广路
}
}
return ans;
}
void printg(int n)//输出网络邻接表
{
cout<<"-----网络邻接表如下：-----"<<endl;
for(int i=1;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
}
void printflow(int n)//输出实流边
{
cout<<"-----实流边如下：-----"<<endl;
for(int i=1;i<=n;i )
for(int j=V[i].first;~j;j=E[j].next)
if(E[j].flow>0)
{
cout<<"v"<<i<<"--"<<"v"<<E[j].v<<" "<<E[j].flow;
cout<<endl;
}
}
int main()
{
int u,v,w;
int n,m;
cout<<"输入节点个数和边数："<<endl;
cin>>n>>m;
init();
cout<<"输入两个节点u，v及边（u--v）的容量w："<<endl;
for(int i=1;i<=m;i )
{
cin>>u>>v>>w;
add(u,v,w);
}
cout<<endl;
printg(n);
cout<<"网络的最大流值："<<Isap(1,n,n)<<endl;
printg(n);
printflow(n);
return 0;
}
```
## 最小费用最大流
### 最小费用路算法
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=100000;
const int N=100;
const int M=10000;
int top;
int dist[N],pre[N];
bool vis[N];
int c[N];
int maxflow;
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow,cost;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
maxflow=0;
}
void add_edge(int u,int v,int c,int cost)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].cost=cost;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c,int cost)
{
add_edge(u,v,c,cost);
add_edge(v,u,0,-cost);
}
bool SPFA(int s,int t,int n)
{
int i,u,v;
queue<int>qu;
memset(vis,false,sizeof(vis));
memset(c,0,sizeof(c));
memset(pre,-1,sizeof(pre));
for(i=1;i<=n;i )
dist[i]=INF;
vis[s]=true;
c[s] ;
dist[s]=0;
qu.push(s);
while(!qu.empty())
{
u=qu.front();
qu.pop();
vis[u]=false;
for(i=V[u].first;i!=-1;i=E[i].next)
{
v=E[i].v;
if(E[i].cap>E[i].flow&&dist[v]>dist[u] E[i].cost)
{
dist[v]=dist[u] E[i].cost;
pre[v]=i;
if(!vis[v])
{
c[v] ;
qu.push(v);
vis[v]=true;
if(c[v]>n)
return false;
}
}
}
}
cout<<"最短路数组"<<endl;
cout<<"dist[ ]=";
for(int i=1;i<=n;i )
cout<<" "<<dist[i];
cout<<endl;
if(dist[t]==INF)
return false;
return true;
}
int MCMF(int s,int t,int n)
{
int d;
int i,mincost;
mincost=0;
while(SPFA(s,t,n))
{
d=INF;
cout<<endl;
cout<<"增广路径："<<t;
for(i=pre[t];i!=-1;i=pre[E[i^1].v])
{
d=min(d,E[i].cap-E[i].flow);
cout<<"--"<<E[i^1].v;
}
cout<<"增流："<<d<<endl;
cout<<endl;
maxflow =d;
for(i=pre[t];i!=-1;i=pre[E[i^1].v])
{
E[i].flow =d;
E[i^1].flow-=d;
}
mincost =dist[t]*d;
}
return mincost;
}
void printg(int n)//输出网络邻接表
{
cout<<"-----网络邻接表如下：-----"<<endl;
for(int i=1;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].cost<<" "<<E[j].next;
cout<<"]"<<endl;
}
cout<<endl;
}
void printflow(int n)//输出实流边
{
cout<<"-----实流边如下：-----"<<endl;
for(int i=1;i<=n;i )
for(int j=V[i].first;~j;j=E[j].next)
if(E[j].flow>0)
{
cout<<"v"<<i<<"--"<<"v"<<E[j].v<<" "<<E[j].flow<<" "<<E[j].cost;
cout<<endl;
}
}
int main()
{
int u,v,w,c;
int n,m;
cout<<"输入节点个数和边数："<<endl;
cin>>n>>m;
init();
cout<<"输入两个节点u，v及边（u--v）的容量w,单位容量费用c："<<endl;
for(int i=1;i<=m;i )
{
cin>>u>>v>>w>>c;
add(u,v,w,c);
}
cout<<endl;
printg(n);
cout<<"网络的最小费用为："<<MCMF(1,n,n)<<endl;
cout<<"网络的最大流值："<<maxflow<<endl;
printg(n);
printflow(n);
return 0;
}
```
### 消圈算法
过程：
1. 找出给定网络的最大流。
2. 在最大流对应的混合网络中找负费用圈。
3. 消负费用圈：负费用圈同方向的边流量加d，反方向的边流量减d。d为负费用圈的所有边的最小可增量cap-flow。
## 配对方案问题
二分图：又称作二部图，是图论中的一种特殊模型。设G=（V，E）是一个无向图，如果节点集V可分割为两个互不相交的子集（V1，V2），并且图中的每条边（i，j）所关联的两个节点i和j分别属于这两个不同的节点集，则称图G为一个二分图。
匹配：在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共节点。
最大匹配：一个图所有匹配中，边数最多的匹配。
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=100000;
const int N=100;
const int M=1000;
int top;
int h[N],pre[N],g[N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c)
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)
{
queue<int>Q;
memset(h,-1,sizeof(h));
memset(g,0,sizeof(g));
h[t]=0;
Q.push(t);
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
E[j].flow =d;
E[j^1].flow-=d;
u=E[j^1].v;
cout<<"--"<<u;
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break;
}
}
if(i==-1)
{
if(--g[h[u]]==0)
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)
if(E[j].cap>E[j].flow)
hmin=min(hmin,h[E[j].v]);
h[u]=hmin 1;
cout<<"重贴标签后高度："<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];
if(u!=s)
u=E[pre[u]^1].v;
}
}
return ans;
}
void printg(int n)//输出网络邻接表
{
cout<<"-----网络邻接表如下：-----"<<endl;
for(int i=0;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
cout<<endl;
}
void printflow(int n)//输出实流边
{
cout<<"-----配对方案如下：-----"<<endl;
for(int i=1;i<=n;i )
for(int j=V[i].first;~j;j=E[j].next)
if(E[j].flow>0)
{
cout<<i<<"--"<<E[j].v<<endl;
break;
}
}
int main()
{
int u,v,total;
int n,m;
cout<<"输入男推销员和女推销员的人数："<<endl;
cin>>m>>n;
init();
total=m n;
for(int i=1;i<=m;i )
add(0,i,1);//源点到女推销员的边
for(int j=m 1;j<=total;j )
add(j,total 1,1);//男推销员到汇点的边
cout<<"输入可以配合的女推销员编号和男推销员编号（两个都为-1结束）："<<endl;
while(cin>>u>>v,u v!=-2)
add(u,v,1);
cout<<endl;
printg(total 2);
cout<<"最大配对数："<<Isap(0,total 1,total 2)<<endl;
cout<<endl;
printg(total 2);
printflow(m);
return 0;
}
```
### 优化--匈牙利算法
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=100000;
const int N=100;
const int M=1000;
int top;
int match[N];
bool vis[N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
memset(match,0,sizeof(match));
}
void add(int u,int v)
{
E[top].v=v;
E[top].next=V[u].first;
V[u].first=top ;
}
bool maxmatch(int u)//为u找匹配点，找到返回true，否则返回false
{
int v;
for(int j=V[u].first;~j;j=E[j].next)//检查u的所有邻接边
{
v=E[j].v;//u的邻接点v
if(!vis[v])
{
vis[v]=1;
if(!match[v]||maxmatch(match[v]))
{ //v未匹配或者为v的匹配点找到了其它匹配
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;//所有的邻接边都检查完毕，未找到匹配点
}
void printg(int n)//输出网络邻接表
{
cout<<"-----网络邻接表如下：-----"<<endl;
for(int i=1;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].next;
cout<<"]"<<endl;
}
cout<<endl;
}
void print(int n)//输出实流边
{
cout<<"-----配对方案如下：-----"<<endl;
for(int i=1;i<=n;i )
if(match[i])
cout<<i<<"--"<<match[i]<<endl;
}
int main()
{
int u,v,total;
int n,m,num=0;
cout<<"输入男推销员和女推销员的人数："<<endl;
cin>>m>>n;
init();
total=m n;
cout<<"输入可以配合的女推销员编号和男推销员编号（两个都为-1结束）："<<endl;
while(cin>>u>>v,u v!=-2)
{
add(u,v);
add(v,u);
}
cout<<endl;
printg(total);
for(int i=1;i<=m;i )
{
memset(vis,0,sizeof(vis));
if(maxmatch(i))
num ;
}
cout<<"最大配对数："<<num<<endl;
cout<<endl;
print(m);
return 0;
}
```
## 圆桌问题
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=10000;
const int N=100;
const int M=1000;
int top;
int h[N],pre[N],g[N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c)
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)
{
queue<int>Q;
memset(h,-1,sizeof(h));
memset(g,0,sizeof(g));
h[t]=0;
Q.push(t);
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
E[j].flow =d;
E[j^1].flow-=d;
u=E[j^1].v;
cout<<"--"<<u;
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break;
}
}
if(i==-1)
{
if(--g[h[u]]==0)
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)
if(E[j].cap>E[j].flow)
hmin=min(hmin,h[E[j].v]);
h[u]=hmin 1;
cout<<"重贴标签后高度："<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];
if(u!=s)
u=E[pre[u]^1].v;
}
}
return ans;
}
void printg(int n)
{
cout<<"-------网络邻接表如下：-------"<<endl;
for(int i=0;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
}
void print(int m)
{
cout<<"安排方案如下："<<endl;
cout<<"每个代表团的安排情况："<<endl;
for(int i=1;i<=m;i )
{
cout<<"第"<<i<<"个代表团的安排的情况："<<endl;
for(int j=V[i].first;~j;j=E[j].next)
if(E[j].flow==1)
cout<<E[j].v-m<<" ";
cout<<endl;
}
}
int main()
{
int n,m,sum=0,total;
int cost;
cout<<"输入代表团数n和会议桌数m:"<<endl;
cin>>m>>n;
init();
total=m n;
cout<<"依次输入每个代表团的人数:"<<endl;
for(int i=1;i<=m;i )
{
cin>>cost;
sum =cost;
add(0,i,cost);
}
cout<<"依次输入每个会议桌可安排人数："<<endl;
for(int j=m 1;j<=total;j )
{
cin>>cost;
add(j,total 1,cost);
}
for(int i=1;i<=m;i )
for(int j=m 1;j<=total;j )
add(i,j,1);
cout<<endl;
printg(total 2);
if(sum==Isap(0,total 1,total 2))
{
cout<<"会议桌安排成功。";
cout<<endl;
print(m);
cout<<endl;
printg(total 2);
}
else
cout<<"无法安排所有代表团。";
return 0;
}
```
## 试题库问题
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=10000;
const int N=100;
const int M=1000;
int top;
int h[N],pre[N],g[N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c)
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)
{
queue<int>Q;
memset(h,-1,sizeof(h));
memset(g,0,sizeof(g));
h[t]=0;
Q.push(t);
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
E[j].flow =d;
E[j^1].flow-=d;
u=E[j^1].v;
cout<<"--"<<u;
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break;
}
}
if(i==-1)
{
if(--g[h[u]]==0)
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)
if(E[j].cap>E[j].flow)
hmin=min(hmin,h[E[j].v]);
h[u]=hmin 1;
cout<<"重贴标签后高度："<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];
if(u!=s)
u=E[pre[u]^1].v;
}
}
return ans;
}
void printg(int n)
{
cout<<"-------网络邻接表如下：-------"<<endl;
for(int i=0;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
}
void print(int m)
{
cout<<"试题抽取方案："<<endl;
for(int i=1;i<=m;i )
{
cout<<"第"<<i<<"个题型抽取的试题号："<<endl;
for(int j=V[i].first;~j;j=E[j].next)
if(E[j].flow==1)
cout<<E[j].v-m<<" ";
cout<<endl;
}
}
int main()
{
int n,m,sum=0,total;
int cost,num;
cout<<"输入题型数m和试题总数n:"<<endl;
cin>>m>>n;
init();
total=m n;
cout<<"依次输入每种题型选择的数量:"<<endl;
for(int i=1;i<=m;i )
{
cin>>cost;
sum =cost;
add(0,i,cost);
}
cout<<"依次输入每个试题所属的题型（0结束）："<<endl;
for(int j=m 1;j<=total;j )
{
while(cin>>num,num)
add(num,j,1);
add(j,total 1,1);
}
cout<<endl;
printg(total 2);
if(sum==Isap(0,total 1,total 2))
{
cout<<"抽取试题成功。";
cout<<endl;
print(m);
cout<<endl;
printg(total 2);
}
else
cout<<"抽取试题不成功。";
return 0;
}
```
## 最大收益问题
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=10000;
const int N=100;
const int M=1000;
int top;
int h[N],pre[N],g[N];
bool flag[N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c)
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)
{
queue<int>Q;
memset(h,-1,sizeof(h));
memset(g,0,sizeof(g));
h[t]=0;
Q.push(t);
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
E[j].flow =d;
E[j^1].flow-=d;
u=E[j^1].v;
cout<<"--"<<u;
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break;
}
}
if(i==-1)
{
if(--g[h[u]]==0)
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)
if(E[j].cap>E[j].flow)
hmin=min(hmin,h[E[j].v]);
h[u]=hmin 1;
cout<<"重贴标签后高度："<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];
if(u!=s)
u=E[pre[u]^1].v;
}
}
return ans;
}
void printg(int n)
{
cout<<"-------网络邻接表如下：-------"<<endl;
for(int i=0;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
}
void DFS(int s)
{
for(int i=V[s].first;~i;i=E[i].next)
if(E[i].cap>E[i].flow)
{
int u=E[i].v;
if(!flag[u])
{
flag[u]=true;
DFS(u);
}
}
}
void print(int m,int n)
{
cout<<"最大收益方案："<<endl;
DFS(0);
cout<<"选中的实验编号："<<endl;
for(int i=1;i<=m;i )
if(flag[i])
cout<<i<<" ";
cout<<endl;
cout<<"选中的仪器编号："<<endl;
for(int i=m 1;i<=m n;i )
if(flag[i])
cout<<i-m<<" ";
}
int main()
{
int n,m,sum=0,total;
int cost,num;
memset(flag,0,sizeof(flag));
cout<<"输入实验数m和仪器数n:"<<endl;
cin>>m>>n;
init();
total=m n;
cout<<"依次输入实验产生的效益和该实验所需要的仪器编号（0结束）:"<<endl;
for(int i=1;i<=m;i )
{
cin>>cost;
sum =cost;
add(0,i,cost);
while(cin>>num,num)
add(i,m num,INF);
}
cout<<"依次输入所有仪器的费用："<<endl;
for(int j=m 1;j<=total;j )
{
cin>>cost;
add(j,total 1,cost);
}
cout<<endl;
printg(total 2);
cout<<"最大净收益："<<sum-Isap(0,total 1,total 2)<<endl;
cout<<endl;
printg(total 2);
cout<<endl;
print(m,n);
return 0;
}
```
## 方格取数问题
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=10000;
const int N=100;
const int M=1000;
int top;
int h[N],pre[N],g[N];
bool flag[N*N];
bool dfsflag[N*N];
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c)
{
add_edge(u,v,c);
add_edge(v,u,0);
}
void set_h(int t,int n)
{
queue<int>Q;
memset(h,-1,sizeof(h));
memset(g,0,sizeof(g));
h[t]=0;
Q.push(t);
while(!Q.empty())
{
int v=Q.front();
Q.pop();
g[h[v]];
for(int i=V[v].first;~i;i=E[i].next)
{
int u=E[i].v;
if(h[u]==-1)
{
h[u]=h[v] 1;
Q.push(u);
}
}
}
cout<<"初始化高度"<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
}
int Isap(int s,int t,int n)
{
set_h(t,n);
int ans=0,u=s;
int d;
while(h[s]<n)
{
int i=V[u].first;
if(u==s)
d=INF;
for(;~i;i=E[i].next)
{
int v=E[i].v;
if(E[i].cap>E[i].flow&&h[u]==h[v] 1)
{
u=v;
pre[v]=i;
d=min(d,E[i].cap-E[i].flow);
if(u==t)
{
cout<<endl;
cout<<"增广路径："<<t;
while(u!=s)
{
int j=pre[u];
E[j].flow =d;
E[j^1].flow-=d;
u=E[j^1].v;
cout<<"--"<<u;
}
cout<<"增流："<<d<<endl;
ans =d;
d=INF;
}
break;
}
}
if(i==-1)
{
if(--g[h[u]]==0)
break;
int hmin=n-1;
for(int j=V[u].first;~j;j=E[j].next)
if(E[j].cap>E[j].flow)
hmin=min(hmin,h[E[j].v]);
h[u]=hmin 1;
cout<<"重贴标签后高度："<<endl;
cout<<"h[]=";
for(int i=1;i<=n;i )
cout<<" "<<h[i];
cout<<endl;
g[h[u]];
if(u!=s)
u=E[pre[u]^1].v;
}
}
return ans;
}
void printg(int n)
{
cout<<"-------网络邻接表如下：-------"<<endl;
for(int i=0;i<=n;i )
{
cout<<"v"<<i<<" ["<<V[i].first;
for(int j=V[i].first;~j;j=E[j].next)
cout<<"]--["<<E[j].v<<" "<<E[j].cap<<" "<<E[j].flow<<" "<<E[j].next;
cout<<"]"<<endl;
}
}
void DFS(int s)
{
for(int i=V[s].first;~i;i=E[i].next)
if(E[i].cap>E[i].flow)
{
int u=E[i].v;
if(!dfsflag[u])
{
dfsflag[u]=true;
DFS(u);
}
}
}
void print(int m,int n)
{
cout<<"最佳方案："<<endl;
cout<<"选中的物品编号:"<<endl;
DFS(0);
for(int i=1;i<=m*n;i )
if((flag[i]&&dfsflag[i])||(!flag[i]&&!dfsflag[i]))
cout<<i<<" ";
cout<<endl;
}
int main()
{
int n,m,sum=0,total;
int map[N][N];
memset(flag,0,sizeof(flag));
memset(dfsflag,0,sizeof(dfsflag));
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
cout<<"输入货架行数m和列数n:"<<endl;
cin>>m>>n;
init();
total=m*n;
cout<<"依次输入每行每个商品的价值:"<<endl;
for(int i=1;i<=m;i )
for(int j=1;j<=n;j )
{
cin>>map[i][j];
sum =map[i][j];
}
for(int i=1;i<=m;i )
for(int j=1;j<=n;j )
{
if((i j)%2==0)
{
add(0,(i-1)*n j,map[i][j]);
flag[(i-1)*n j]=1;
for(int k=0;k<4;k )
{
int x=i dir[k][0];
int y=j dir[k][1];
if(x<=m&&x>0 && y<=n&&x>0)
add((i-1)*n j,(x-1)*n y,INF);
}
}
else
add((i-1)*n j,total 1,map[i][j]);
}
cout<<endl;
printg(total 2);
cout<<"最大价值："<<sum-Isap(0,total 1,total 2)<<endl;
cout<<endl;
printg(total 2);
cout<<endl;
print(m,n);
return 0;
}
```
## 旅游路线问题
```c
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
const int INF=10000;
const int M=100;
const int N=1000;
int top;
int dist[N],pre[N];
bool vis[N];
int c[N];
int maxflow,mincost;
string str[M];
map<string,int> maze;
struct Vertex
{
int first;
}V[N];
struct Edge
{
int v,next;
int cap,flow,cost;
}E[M];
void init()
{
memset(V,-1,sizeof(V));
top=0;
}
void add_edge(int u,int v,int c,int cost)
{
E[top].v=v;
E[top].cap=c;
E[top].flow=0;
E[top].cost=cost;
E[top].next=V[u].first;
V[u].first=top ;
}
void add(int u,int v,int c,int cost)
{
add_edge(u,v,c,cost);
add_edge(v,u,0,-cost);
}
bool SPFA(int s,int t,int n)
{
int i,u,v;
queue<int> qu;
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
memset(pre,-1,sizeof(pre));
for(i=1;i<=n;i )
dist[i]=INF;
vis[s]=true;
c[s] ;
dist[s]=0;
qu.push(s);
while(!qu.empty())
{
u=qu.front();
qu.pop();
vis[u]=false;
for(i=V[u].first;i!=-1;i=E[i].next)
{
v=E[i].v;
if(E[i].cap>E[i].flow&&dist[v]>dist[u] E[i].cost)
{
dist[v]=dist[u] E[i].cost;
pre[v]=i;
if(!vis[v])
{
c[v] ;
qu.push(v);
vis[v]=true;
if(c[v]>n)
return false;
}
}
}
}
cout<<"最短路数组"<<endl;
cout<<"dist[]=";
for(int i=1;i<=n;i )
cout<<" "<<dist[i];
cout<<endl;
if(dist[t]==INF)
return false;
return true;
}
int MCMF(int s,int t,int n)
{
int d;
maxflow=mincost=0;
while(SPFA(s,t,n))
{
d=INF;
cout<<endl;
cout<<"增广路径："<<t;
for(int i=pre[t];i!=-1;i=pre[E[i^1].v])
{
d=min(d,E[i].cap-E[i].flow);
cout<<"--"<<E[i^1].v;
}
cout<<"增流："<<d<<endl;
cout<<endl;
for(int i=pre[t];i!=-1;i=pre[E[i^1].v])
{
E[i].flow =d;
E[i^1].flow-=d;
}
maxflow =d;
mincost =dist[t]*d;
}
return maxflow;
}
void print(int s,int t)
{
int v;
vis[s]=1;
for(int i=V[s].first;~i;i=E[i].next)
if(!vis[v=E[i].v]&&((E[i].flow>0&&E[i].cost<=0)||(E[i].flow<0&&E[i].cost>=0)))
{
print(v,t);
if(v<=t)
cout<<str[v]<<endl;
}
}
int main()
{
int n,m,i;
string str1,str2;
cout<<"输入景点个数n和直达路线数m："<<endl;
cin>>n>>m;
init();
maze.clear();
cout<<"输入景点名str"<<endl;
for(i=1;i<=n;i )
{
cin>>str[i];
maze[str[i]]=i;
if(i==1||i==n)
add(i,i n,2,0);
else
add(i,i n,1,0);
}
cout<<"输入可以直接到达的两个景点名str1,str2"<<endl;
for(i=1;i<=m;i )
{
cin>>str1>>str2;
int a=maze[str1],b=maze[str2];
if(a<b)
{
if(a==1&&b==n)
add(a n,b,2,-1);
else
add(a n,b,1,-1);
}
else
{
if(b==1&&a==n)
add(b n,a,2,-1);
else
add(b n,a,1,-1);
}
}
if(MCMF(1,2*n,2*n)==2)
{
cout<<"最多经过的景点个数："<<-mincost<<endl;
cout<<"依次经过的景点："<<endl;
cout<<str[1]<<endl;
memset(vis,0,sizeof(vis));
print(1,n);
cout<<str[1]<<endl;
}
else
cout<<"no solution!"<<endl;
return 0;
return 0;
}
```
## 解题秘籍
1. 如果可以使用网络，则构建网络图，如果需要添加源点和汇点则添加之，并确定每条边的容量。
2. 如果可以用最大流解决，求解最大流就可以了。
3. 问题的解不能直接用最大流解决，需要分析问题的解，是不是最小割容量，还是与最小割容量相关的表达式。最小割容量等于最大流值，所以可以通过求解最大流间接得到。
4. 优的问题可以转化为最小费用最大流问题。
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论