怀化网站建设网站,免费云主机哪个好,装修网站建设网,上海定制化网站开发一. 图论
1.最小生成树
图的生成树是它的一颗含有其所有顶点的无环连通子图,一 幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和) 最小的生成树 • 适用场景#xff1a;道路规划、通讯网络规划、管道铺设、电线布设等
题目数据 kruskal算法 稀疏图#x…一. 图论
1.最小生成树
图的生成树是它的一颗含有其所有顶点的无环连通子图,一 幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和) 最小的生成树 • 适用场景道路规划、通讯网络规划、管道铺设、电线布设等
题目数据 kruskal算法 稀疏图按边大小排序
#includebits/stdc.h
using namespace std;
const int maxn5e33,maxm2e55;int n,m;
struct node{int fr,to,val;inline bool operator(node b)const {return valb.val;}
}e[maxm1];
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 i1;im;i) {scanf(%d %d %d,x,y,z);add(x,y,z);add(x,y,z);//无向图 }sort(e1,ek1); //边排序for(int i1;in;i)fa[i]i;//并查集初始化int cnt0,ans0;for(int i1;ik;i){int xfind(e[i].fr),yfind(e[i].to);if(x!y){fa[x]y;//连边anse[i].val;cnt;if(cntn-1)break;}}if(cntn-1)printf(%d,ans);else puts(orz);//图不连通return 0;
}prim 稠密图
#includebits/stdc.h
#define re return
#define inc(i,l,r) for(int il;ir;i)
using namespace std;const int maxn5e33,maxm2e55;
int inf5e8;
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 ans0,cntn-1;while(cnt--)//需要进行n-1次循环 {int now,minninf;inc(i,1,n)if(!vis[i]dis[i]minn)minndis[i],nowi;//找当前最短距离点 nowif(minninf){printf(orz);re 0;} vis[now]1;ansdis[now];inc(i,1,n)dis[i]min(dis[i],d[now][i]);}printf(%d,ans);re 0;
}2.网络流
通常可以把这些边想象成道路流量就是这条道 路的车流量容量就是道路可承受的最大的车流量 • 适用场景企业生产运输问题、交通拥堵优化问题等
最大流 题目数据
#includebits/stdc.h
#define re return
#define inc(i,l,r) for(int il;ir;i)
using namespace std;
templatetypename Tinline void rd(Tx)
{char c;bool f0;while((cgetchar())0||c9)if(c-)f1;xc^48;while((cgetchar())0c9)xx*10(c^48);if(f)x-x;
}
const int maxn1e44,maxm1e55;
int n,m,hd[maxn],s,t;
struct node{int to,nt,w;
}e[maxm1];
int k1;
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;queueintq;q.push(s);while(!q.empty()){int xq.front();q.pop();for(int ihd[x];i;ie[i].nt){int ve[i].to;if(!deep[v]e[i].w){deep[v]deep[x]1;if(vt)re 1;q.push(v);}}}re 0;
}inline int dfs(int x,int flow)
{if(xt)re flow;int deltaflow;for(int icur[x];i;ie[i].nt){int ve[i].to;if(deep[v]deep[x]1e[i].w){int ddfs(v,min(e[i].w,delta));e[i].w-d;e[i^1].wd;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 ans0;while(bfs()){inc(i,1,n)cur[i]hd[i];ansdfs(s,2147483647);}printf(%d,ans);re 0;
}最小费用最大流 最大流量的基础上要求最小的费用有边权值 题目数据
#includebits/stdc.h
#define re return
#define inc(i,l,r) for(int il;ir;i)
using namespace std;
templatetypename Tinline void rd(Tx)
{char c;bool f0;while((cgetchar())0||c9)if(c-)f1;xc^48;while((cgetchar())0c9)xx*10(c^48);if(f)x-x;
}
const int maxn5e33;int k1,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].tov;e[k].nthd[u];e[k].floww;e[k].costf;hd[u]k;
}inline bool spfa()
{queueintq;memset(dis,0x3f3f3f3f,sizeof dis);memset(vis,0,sizeof vis);q.push(s);dis[s]0;flow[s]0x3f3f3f3f;while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int ihd[x];i;ie[i].nt){int ve[i].to,we[i].flow,fe[i].cost;if(wdis[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 xt;while(x!s){int iord[x];e[i].flow-flow[t];e[i^1].flowflow[t];xe[i^1].to;}sflowflow[t];smoneyflow[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 单源最短路 容易被卡 #includebits/stdc.h
#define re return
#define inc(i,l,r) for(int il;ir;i)
using namespace std;
templatetypename Tinline void rd(Tx)
{char c;bool f0;while((cgetchar())0||c9)if(c-)f1;xc^48;while((cgetchar())0c9)xx*10(c^48);if(f)x-x;
}const int maxn1e45,maxm5e55;
int n,m,hd[maxn];
struct node{int to,nt,val;
}e[maxm1];
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 inf2147483647,dis[maxn],vis[maxn];
inline void spfa()
{inc(i,1,n)dis[i]inf;dis[s]0;queueintq;q.push(s);while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int ihd[x];i;ie[i].nt){int ve[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 单源最短路 无负边 #includebits/stdc.h
#define re return
#define inc(i,l,r) for(int il;ir;i)
using namespace std;
templatetypename Tinline void rd(Tx)
{char c;bool f0;while((cgetchar())0||c9)if(c-)f1;xc^48;while((cgetchar())0c9)xx*10(c^48);if(f)x-x;
}const int maxn1e45,maxm5e55;
int n,m,hd[maxn];
struct node{int to,nt,val;
}e[maxm1];
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 inf2147483647,dis[maxn];
struct KKK{
int x,val;
inline bool operator(KKK u)const
{re valu.val;
}
};
inline void dij()
{inc(i,1,n)dis[i]inf;dis[s]0;priority_queueKKKq;q.push((KKK){s,0});while(!q.empty()){KKK uq.top();q.pop();int xu.x;if(dis[x]!u.val)continue;for(int ihd[x];i;ie[i].nt){int ve[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) 多源最短路 #includebits/stdc.h
using namespace std;
#define inf 1234567890
#define maxn 10005
inline int read()
{int x0,k1; char cgetchar();while(c0||c9){if(c-)k-1;cgetchar();}while(c0c9)x(x3)(x1)(c^48),cgetchar();return x*k;
}//快读
int a[maxn][maxn],n,m,s;
inline void floyd()
{for(int k1;kn;k)//这里要先枚举k可以理解为中转点{for(int i1;in;i){if(ik||a[i][k]inf){continue;}for(int j1;jn;j){a[i][j]min(a[i][j],a[i][k]a[k][j]);//松弛操作即更新每两个点之间的距离//松弛操作有三角形的三边关系推出//即两边之和大于第三边}}}
}
int main()
{nread(),mread(),sread();for(int i1;in;i){for(int j1;jn;j){a[i][j]inf;}}//初始化相当于memset(a,inf,sizeof(a))for(int i1,u,v,w;im;i){uread(),vread(),wread();a[u][v]min(a[u][v],w);//取min可以对付重边}floyd();a[s][s]0;for(int i1;in;i){printf(%d ,a[s][i]);}return 0;
}二、动态规划
dp数学建模的应用不多感觉主要还是各种环境下的一个背包多维dp对于状压数位都不怎么涉及 总的思想来说偏向背包较为单一找递归方程时的问题主要在于结合其他信息可能涉及到概率马尔科夫链图偏向树形dp之类的
背包 采药 一维
#includebits/stdc.h
using namespace std;
int a[100001];
int o;
int main()
{int t,m;cintm;
int w[m1],v[m1];
for(int i1;im;i)
cinw[i]v[i];for(int j1;jt;j) for(int k1;km;k){a[j]o;if(jw[k]){a[j]max(a[j],a[j-w[k]]v[k]); omax(o,a[j]);}}couta[t];return 0;
}二维
#includebits/stdc.h
using namespace std;
int a[101][1001];
int main()
{
int n,m;
cinnm;
int w[m1];
int v[m1];
for(int i1;im;i)
cinw[i]v[i];for(int i1;im;i)
for(int j1;jn;j)
{ a[i][j]a[i-1][j];
if(jw[i])a[i][j]max(a[i-1][j-w[i]]v[i],a[i][j]); }
couta[m][n];
return 0;
}2.树形dp 在连通图上dp 没有上司的舞会
#includebits/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 ihead[x];i!0;icc[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 i1;in;i)
scanf(%d,f[i][1]);for(int i1;in;i)
{scanf(%d%d,a,b);
cc[a]head[b];
head[b]a;in[a]1;}for(int i1;in;i)
if(in[i]0){ci;break;}
dfs(c);
printf(%d,max(f[c][1],f[c][0]));return 0;
}三、启发式算法
模拟退火 模拟退火算法Simulate AnnealSA是一种通用概率演算法用来在一个大的搜寻空间内找寻命题的最优解。 https://www.cnblogs.com/flashhu/p/8884132.html
#includebits/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 il;ir;i)
#define dec(i,l,r) for(register int il;ir;--i)using namespace std;
int n,x[1005],y[1005],w[1005];
double EPS10e-15,D0.975;double calc(double x0,double y0)
{double res0;inc(i,1,n)ressqrt((x[i]-x0)*(x[i]-x0)(y[i]-y0)*(y[i]-y0))*w[i];re res;
}int main()
{
// freopen(in.txt,r,stdin);double x10,y10,x0,y0,bx,by,res,ans,best,time2;scanf(%d,n);inc(i,1,n){scanf(%d%d%d,x[i],y[i],w[i]);bxx[i];byy[i];}bestcalc(bx/n,by/n);//用平均值作为最初解srand(20130317);while(time--){x1bx,y1by,ansbest;for(double T100000;TEPS;T*D){x0x1T*(2*rand()-RAND_MAX);y0y1T*(2*rand()-RAND_MAX);rescalc(x0,y0);if(resbest){bestres;bxx0;byy0;}if(resans||exp((ans-res)/T)(double)(rand())/RAND_MAX){ansres;x1x0;y1y0;}}}printf(%.3lf %.3lf,bx,by);re 0;
}
