最优化方法

一. 图论

1.最小生成树

图的生成树是它的一颗含有其所有顶点的无环连通子图,一 幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和) 最小的生成树
• 适用场景：道路规划、通讯网络规划、管道铺设、电线布设等

题目数据
kruskal算法
稀疏图，按边大小排序

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+3,maxm=2e5+5;int n,m;
struct node{int fr,to,val;inline bool operator<(node b)const {return val<b.val;}
}e[maxm<<1];
int k,fa[maxn];
inline void add(int x,int y,int z){e[++k]=(node){x,y,z};}inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{scanf("%d %d",&n,&m);int x,y,z;for(int i=1;i<=m;i++) {scanf("%d %d %d",&x,&y,&z);add(x,y,z);add(x,y,z);//无向图 }sort(e+1,e+k+1); //边排序for(int i=1;i<=n;i++)fa[i]=i;//并查集初始化int cnt=0,ans=0;for(int i=1;i<=k;i++){int x=find(e[i].fr),y=find(e[i].to);if(x!=y){fa[x]=y;//连边ans+=e[i].val;++cnt;if(cnt==n-1)break;}}if(cnt==n-1)printf("%d",ans);else puts("orz");//图不连通return 0;
}

prim
稠密图

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;const int maxn=5e3+3,maxm=2e5+5;
int inf=5e8;
int n,m,d[maxn][maxn],dis[maxn],vis[maxn];
int main()
{// freopen("a.in","r",stdin);scanf("%d %d",&n,&m);int x,y,z;inc(i,1,n)inc(j,1,n)d[i][j]=inf;inc(i,1,m){scanf("%d %d %d",&x,&y,&z);d[x][y]=d[y][x]=min(d[x][y],z);}vis[1]=1;//将1号点加入图中 inc(i,2,n)dis[i]=d[1][i];//dis初始化为1到各个点之间的最短距离 int ans=0,cnt=n-1;while(cnt--)//需要进行n-1次循环 {int now,minn=inf;inc(i,1,n)if(!vis[i]&&dis[i]<minn)minn=dis[i],now=i;//找当前最短距离点 nowif(minn==inf){printf("orz");re 0;}   vis[now]=1;ans+=dis[now];inc(i,1,n)dis[i]=min(dis[i],d[now][i]);}printf("%d",ans);re 0;
}

2.网络流

通常可以把这些边想象成道路，流量就是这条道 路的车流量，容量就是道路可承受的最大的车流量 • 适用场景：企业生产运输问题、交通拥堵优化问题等

最大流
题目数据

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{char c;bool f=0;while((c=getchar())<'0'||c>'9')if(c=='-')f=1;x=c^48;while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);if(f)x=-x;
}
const int maxn=1e4+4,maxm=1e5+5; 
int n,m,hd[maxn],s,t;
struct node{int to,nt,w;
}e[maxm<<1];
int k=1;
inline void add(int x,int y,int z)
{e[++k]=(node){y,hd[x],z};hd[x]=k;e[++k]=(node){x,hd[y],0};hd[y]=k;
}int deep[maxn],cur[maxn];
inline bool bfs()
{inc(i,1,n)deep[i]=0;deep[s]=1;queue<int>q;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=hd[x];i;i=e[i].nt){int v=e[i].to;if(!deep[v]&&e[i].w){deep[v]=deep[x]+1;if(v==t)re 1;q.push(v);}}}re 0;
}inline int dfs(int x,int flow)
{if(x==t)re flow;int delta=flow;for(int &i=cur[x];i;i=e[i].nt){int v=e[i].to;if(deep[v]==deep[x]+1&&e[i].w){int d=dfs(v,min(e[i].w,delta));e[i].w-=d;e[i^1].w+=d;delta-=d;if(!delta)re flow;}}re flow-delta;
}
int main()
{rd(n),rd(m),rd(s),rd(t);int x,y,w;inc(i,1,m){rd(x),rd(y),rd(w);add(x,y,w);}int ans=0;while(bfs()){inc(i,1,n)cur[i]=hd[i];ans+=dfs(s,2147483647);}printf("%d",ans);re 0;
}

最小费用最大流
最大流量的基础上要求最小的费用，有边权值
题目数据

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{char c;bool f=0;while((c=getchar())<'0'||c>'9')if(c=='-')f=1;x=c^48;while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);if(f)x=-x;
}
const int maxn=5e3+3;int k=1,n,m,s,t;
int dis[maxn],ord[maxn],hd[maxn],flow[maxn],vis[maxn];
int smoney,sflow;struct node{int flow,to,nt,cost;
}e[100005];
inline void add(int u,int v,int w,int f)
{e[++k].to=v;e[k].nt=hd[u];e[k].flow=w;e[k].cost=f;hd[u]=k;
}inline bool spfa()
{queue<int>q;memset(dis,0x3f3f3f3f,sizeof dis);memset(vis,0,sizeof vis);q.push(s);dis[s]=0;flow[s]=0x3f3f3f3f;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=hd[x];i;i=e[i].nt){int v=e[i].to,w=e[i].flow,f=e[i].cost;if(w&&dis[v]>dis[x]+f){if(!vis[v]){vis[v]=1;q.push(v);}flow[v]=min(flow[x],w);dis[v]=dis[x]+f;ord[v]=i;}}}re dis[t]!=0x3f3f3f3f;
}inline void vivi()
{int x=t;while(x!=s){int i=ord[x];e[i].flow-=flow[t];e[i^1].flow+=flow[t];x=e[i^1].to;}sflow+=flow[t];smoney+=flow[t]*dis[t];
}
int main()
{
//	freopen("a.in","r",stdin);rd(n),rd(m),rd(s),rd(t);int u,v,w,f;inc(i,1,m){rd(u),rd(v),rd(w),rd(f);add(u,v,w,f);add(v,u,0,-f);}while(spfa())vivi();printf("%d %d",sflow,smoney);re 0;
}

3.最短路

主要包括Dijkstra算法和Floyd算法两种，用于求解 两点间的最短距离 • 适用场景：路径规划问题，如修建道路、设定救援路线等
题目数据

spfa

单源最短路
容易被卡

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{char c;bool f=0;while((c=getchar())<'0'||c>'9')if(c=='-')f=1;x=c^48;while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);if(f)x=-x;
}const int maxn=1e4+5,maxm=5e5+5;
int n,m,hd[maxn];
struct node{int to,nt,val;
}e[maxm<<1];
int k,s;
inline void add(int x,int y,int z){e[++k]=(node){y,hd[x],z};hd[x]=k;
}#define ll long long
ll inf=2147483647,dis[maxn],vis[maxn];
inline void spfa()
{inc(i,1,n)dis[i]=inf;dis[s]=0;queue<int>q;q.push(s);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=hd[x];i;i=e[i].nt){int v=e[i].to;if(dis[v]>dis[x]+e[i].val){dis[v]=dis[x]+e[i].val;if(!vis[v]){vis[v]=1;q.push(v);    }}}}
}int main()
{// freopen("a.in","r",stdin);rd(n),rd(m),rd(s);int x,y,z;inc(i,1,m){rd(x),rd(y),rd(z);add(x,y,z);}spfa();inc(i,1,n)printf("%lld ",dis[i]);re 0;
}

dijsktra

单源最短路
无负边

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{char c;bool f=0;while((c=getchar())<'0'||c>'9')if(c=='-')f=1;x=c^48;while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);if(f)x=-x;
}const int maxn=1e4+5,maxm=5e5+5;
int n,m,hd[maxn];
struct node{int to,nt,val;
}e[maxm<<1];
int k,s;
inline void add(int x,int y,int z){e[++k]=(node){y,hd[x],z};hd[x]=k;
}#define ll long long
ll inf=2147483647,dis[maxn];
struct KKK{
int x,val;
inline bool operator<(KKK u)const 
{re val>u.val;
}
};
inline void dij()
{inc(i,1,n)dis[i]=inf;dis[s]=0;priority_queue<KKK>q;q.push((KKK){s,0});while(!q.empty()){KKK u=q.top();q.pop();int x=u.x;if(dis[x]!=u.val)continue;for(int i=hd[x];i;i=e[i].nt){int v=e[i].to;if(dis[v]>dis[x]+e[i].val){dis[v]=dis[x]+e[i].val;q.push((KKK){v,dis[v]});}}}
}int main()
{//freopen("a.in","r",stdin);rd(n),rd(m),rd(s);int x,y,z;inc(i,1,m){rd(x),rd(y),rd(z);add(x,y,z);}dij();inc(i,1,n)printf("%lld ",dis[i]);re 0;
}

floyd

O(n^3)
多源最短路

#include<bits/stdc++.h>
using namespace std;
#define inf 1234567890
#define maxn 10005
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}//快读
int a[maxn][maxn],n,m,s;
inline void floyd()
{for(int k=1;k<=n;k++)//这里要先枚举k（可以理解为中转点）{for(int i=1;i<=n;i++){if(i==k||a[i][k]==inf){continue;}for(int j=1;j<=n;j++){a[i][j]=min(a[i][j],a[i][k]+a[k][j]);//松弛操作，即更新每两个点之间的距离//松弛操作有三角形的三边关系推出//即两边之和大于第三边}}}
}
int main()
{n=read(),m=read(),s=read();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=inf;}}//初始化，相当于memset(a,inf,sizeof(a))for(int i=1,u,v,w;i<=m;i++){u=read(),v=read(),w=read();a[u][v]=min(a[u][v],w);//取min可以对付重边}floyd();a[s][s]=0;for(int i=1;i<=n;i++){printf("%d ",a[s][i]);}return 0;
}

二、动态规划

dp数学建模的应用不多，感觉主要还是各种环境下的一个背包（多维dp），对于状压，数位都不怎么涉及
总的思想来说偏向背包较为单一，找递归方程时的问题主要在于结合其他信息，可能涉及到概率（马尔科夫链），图（偏向树形dp之类的）

1. 背包
   采药
   一维

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int o;
int main()
{int t,m;cin>>t>>m;
int w[m+1],v[m+1];
for(int i=1;i<=m;i++)
cin>>w[i]>>v[i];for(int j=1;j<=t;j++)	for(int k=1;k<=m;k++){a[j]=o;if(j>=w[k]){a[j]=max(a[j],a[j-w[k]]+v[k]); o=max(o,a[j]);}}cout<<a[t];return 0;
}

二维

#include<bits/stdc++.h>
using namespace std;
int a[101][1001];
int main()
{
int n,m;
cin>>n>>m;
int w[m+1];
int v[m+1];
for(int i=1;i<=m;i++)
cin>>w[i]>>v[i];for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{ a[i][j]=a[i-1][j];
if(j>=w[i])a[i][j]=max(a[i-1][j-w[i]]+v[i],a[i][j]); }
cout<<a[m][n];
return 0;
}

2.树形dp
在连通图上dp
没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
int f[6005][3],head[6005],cc[6005],in[6005];
int n,a,b,c;void dfs(int x)
{   for(int i=head[x];i!=0;i=cc[i]){	dfs(i);f[x][1]=f[x][1]+f[i][0];f[x][0]+=max(f[i][0],f[i][1]);}
}int main()
{  scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&f[i][1]);for(int i=1;i<n;i++)
{scanf("%d%d",&a,&b); 
cc[a]=head[b];
head[b]=a;in[a]=1;}for(int i=1;i<=n;i++)
if(in[i]==0){c=i;break;}
dfs(c);
printf("%d",max(f[c][1],f[c][0]));return 0;
}

三、启发式算法

模拟退火
模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。
https://www.cnblogs.com/flashhu/p/8884132.html

#include<bits/stdc++.h>
#define re return
#define st static
#define mem(a,b) memset((a),(b),sizeof(a))
#define inc(i,l,r) for(register int i=l;i<=r;++i)
#define dec(i,l,r) for(register int i=l;i>=r;--i)using namespace std;
int n,x[1005],y[1005],w[1005];
double EPS=10e-15,D=0.975;double calc(double x0,double y0)
{double res=0;inc(i,1,n)res+=sqrt((x[i]-x0)*(x[i]-x0)+(y[i]-y0)*(y[i]-y0))*w[i];re res;
}int main()
{
//	freopen("in.txt","r",stdin);double x1=0,y1=0,x0,y0,bx,by,res,ans,best,time=2;scanf("%d",&n);inc(i,1,n){scanf("%d%d%d",&x[i],&y[i],&w[i]);bx+=x[i];by+=y[i];}best=calc(bx/=n,by/=n);//用平均值作为最初解srand(20130317);while(time--){x1=bx,y1=by,ans=best;for(double T=100000;T>EPS;T*=D){x0=x1+T*(2*rand()-RAND_MAX);y0=y1+T*(2*rand()-RAND_MAX);res=calc(x0,y0);if(res<best){best=res;bx=x0;by=y0;}if(res<ans||exp((ans-res)/T)>(double)(rand())/RAND_MAX){ans=res;x1=x0;y1=y0;}}}printf("%.3lf %.3lf",bx,by);re 0;
}