图论模板 最短路+最小生成树
5.21 最小生成树 Prime
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;//无穷大
int n,ans=0,g[105][105],dis[105],vis[105];
struct edge
{
int u,v,d;//边的起点、终点、权值
bool operator < (const edge &a) const
{
return d>a.d;
}
};
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
if(g[i][j]==0)
g[i][j]=INF;
}
priority_queue<edge> q;//优先队列
int temp=1,cnt=0;//当前顶点和边数
for(int i=1;i<=n;i++)
{
if(i!=temp)
{
dis[i]=g[temp][i];
q.push({temp,i,g[temp][i]});
}
}//从结点1开始
while(!q.empty())
{
edge t=q.top();
q.pop();
int u=t.u,v=t.v,d=t.d;
if(vis[v]) continue;//已经在已加入点的集合当中
vis[v]=1;
cnt++;
cout<<v<<" "<<u<<" "<<d<<endl;
//ans+=t.d;
if(cnt==n-1) break;
temp=v;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&g[temp][i]<dis[i])
{
dis[i]=g[temp][i];
q.push({temp,i,g[temp][i]});
}
}//更新优先队列
}
//cout<<ans<<endl;
return 0;
}
5.21 最小生成树 Kruskal
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m=0,ans=0,g[105][105];//顶点数n，边数m
int p[105];//并查集的父节点
struct edge
{
int u,v,w;//边的顶点和权值
}e[105];
bool cmp(edge a,edge b)//边的权值比较
{
return a.w<b.w;
}
int find(int x)//并查集操作
{
return p[x]==x ? x:p[x]=find(p[x]);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(g[i][j]!=0)
e[++m]={i,j,g[i][j]};
}//存入每条边
sort(e+1,e+m+1,cmp);//按边的权值排序
for(int i=1;i<=n;i++)//并查集父节点初始化
p[i]=i;
for(int i=1;i<=m;i++)//依次考虑每条边
{
int u=e[i].u,v=e[i].v,w=e[i].w;
int x=find(u);
int y=find(v);
if(x!=y)
{
cout<<u<<" "<<v<<" "<<w<<endl;//输出加入的边
p[x]=y;//合并
//ans+=w;
}
}
//cout<<ans<<endl;
return 0;
}
5.28 单源最短路径 Dijkstra
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int INF=0x3f3f3f3f;//无穷大
int n,g[105][105],dis[105],pre[105],vis[105];
struct edge
{
int u,v,d;//边的起点、终点、权值
bool operator < (const edge &a) const
{
return d>a.d;
}
};
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
if(g[i][j]==0)
g[i][j]=INF;
}
priority_queue<edge> q;//优先队列
int temp=1,cnt=0;//当前顶点和边数
for(int i=1;i<=n;i++)
{
if(i!=temp)
{
pre[i]=temp;
dis[i]=g[temp][i];
q.push({temp,i,g[temp][i]});
}
}//从结点temp开始，此题为从结点1开始
while(!q.empty())
{
edge t=q.top();
q.pop();
int v=t.v;
if(vis[v]) continue;//已经在已加入点的集合当中
vis[v]=1;
cnt++;
if(cnt==n-1) break;
temp=v;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&dis[temp]+g[temp][i]<dis[i])
{
dis[i]=dis[temp]+g[temp][i];
pre[i]=temp;
q.push({temp,i,dis[temp]+g[temp][i]});
}
}//更新优先队列
}
for(int i=2;i<=n;i++)
{
if(dis[i]==INF)
{
cout<<"inf: 1->"<<i<<endl;
continue;
}//如果源1到该顶点没有路，则输出："inf: 1->u"
stack<int> s;
int t=i;
while(t!=0)
{
s.push(t);
t=pre[t];
}
cout<<dis[i]<<": "<<s.top();
s.pop();
while(!s.empty())
{
cout<<"->"<<s.top();
s.pop();
}
cout<<endl;
}//输出结果
return 0;
}
A - Frogger（Floyd）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
double x[201],y[201],map[201][201];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1,n;
while(cin>>n)
{
if(n==0) break;
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=min(map[i][j],max(map[i][k],map[k][j]));//Floyd算法，注意这里是求最短的最长边
printf("Scenario #%d\nFrog Distance = %.3f\n\n",t,map[1][2]);
t++;
}
return 0;
}
B - Heavy Transportation（Dijkstra）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int vis[1005],dis[1005],map[1005][1005];
int dijkstra(int n)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
dis[i]=map[1][i];
for(int i=1;i<n;i++)
{
int k=0,maxmin=0;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]>maxmin)
{
maxmin=dis[j];
k=j;
}
vis[k]=1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]<min(dis[k],map[k][j]))
dis[j]=min(dis[k],map[k][j]);
}//注意这道题是找最大的最小值
return dis[n];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t,s=1;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
memset(dis,0,sizeof(dis));
memset(map,0,sizeof(map));//这道题map初始化为0，和一般题不同
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
map[a][b]=map[b][a]=c;
}
printf("Scenario #%d:\n%d\n\n",s++,dijkstra(n));
}
return 0;
}
C - Silver Cow Party（Dijkstra）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define inf 99999999
using namespace std;
int vis[1005],dis1[1005],dis2[1005],map[1005][1005];
void dijkstra(int x,int n,int dis[])//添加数组参数dis，因为这里要算n头牛的最短路径
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
dis[i]=map[x][i];//注意以x为原点
for(int i=1;i<n;i++)
{
int k=0,minn=inf;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]<minn)
{
minn=dis[j];
k=j;
}
vis[k]=1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]>dis[k]+map[k][j])
dis[j]=dis[k]+map[k][j];
}
}//最短路径问题，dijkstra算法
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,x;
cin>>n>>m>>x;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) map[i][j]=0;
else map[i][j]=inf;//图的初始化
for(int i=1;i<=m;i++)
{
int a,b,t;
cin>>a>>b>>t;
map[a][b]=t;
}//边的输入
dijkstra(x,n,dis1);//从聚会回原农场的距离
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
swap(map[i][j],map[j][i]);//map矩阵的转置
dijkstra(x,n,dis2);//从原农场去聚会的距离
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dis1[i]+dis2[i]);
cout<<ans<<endl;
return 0;
}
I - Agri-Net（Prim）
#include <iostream>
#include <cstring>
#define inf 99999999
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,vis[105],dis[105],map[105][105];
while(cin>>n)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(map,0,sizeof(map));//此题输入完整的邻接矩阵，注意一般的初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>map[i][j];
for(int i=1;i<=n;i++)
dis[i]=map[1][i];
for(int i=1;i<=n;i++)
{
int minn=inf,k=0;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]<minn)
{
minn=dis[j];
k=j;
}
vis[k]=1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&dis[j]>map[k][j])
dis[j]=map[k][j];
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=dis[i];
cout<<ans<<endl;
}//最小生成树，Prim算法
return 0;
}