后天要去最后一场区域赛了，文字先鸽
打完润了
目录
问题 F: 图的最短路径-Floyd算法输出最短路径包含的边
问题 A: 图的最小生成树-Prim算法
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N = 110;
int arr[100][100];
int cost[N],adj[N];
signed main(){
int n;
cin>>n;
fer(i,0,n-1){
fer(j,0,n-1){
cin>>arr[i][j];
}
}
fer(i,0,n-1){
if(arr[0][i]!=0){
cout<<i<<" "<<arr[0][i]<<" "<<"0"<<'\n';
}
else{
cout<<i<<" - -"<<'\n';
}
}
}问题 B: 图的最小生成树-Kruskal算法
这题非要这咱手写排序
巨**
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,M=N*2;
struct edg
{
int arc,ver,c;
};
signed main()
{
int n;
cin>>n;
vector<edg> g;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int x;
cin>>x;
if(x)
{
g.push_back({i,j,x});
}
}
}
for(int i=0;i<g.size();i++)
{
for(int j=i+1;j<g.size();j++)
{
if(g[i].c>g[j].c)
{
swap(g[i],g[j]);
}
}
}
for(int i=0;i<g.size();i++){
cout<<"<"<<g[i].arc<<","<<g[i].ver<<">"<<":"<<g[i].c<<'\n';
}
}问题 C: 算法7-9：最小生成树
kruskal板子
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,M=N*2;
int p[N];
const int INF=1000000007;
struct Edge
{
int a,b,w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int n,m;
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i]=i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
signed main(){
cin>>n;
fer(i,1,n){
fer(j,1,n){
int xx;
cin>>xx;
if(xx){
edges[m]={i,j,xx};
m++;
}
}
}
cout<<kruskal();
}问题 D: 算法7-15：迪杰斯特拉最短路径算法
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,inf=0x3f3f3f3f;
int w[N][N];
int dist[N];
int vis[N];
void dijistra(int n,int be){
memset(dist,0x3f,sizeof dist);
vis[be]=1;
dist[be]=0;
int now=be;
for(int i=0;i<n-1;i++){
for( int j=0;j<n;j++){
if(w[now][j]==0||vis[j]==1) continue;
dist[j]=min(dist[j],dist[now]+w[now][j]);
}
int ne=0,minn=inf;
for( int j=0;j<n;j++){
if(vis[j]==1) continue;
if(dist[j]<minn){
minn=dist[j];
ne=j;
}
}
now=ne;
vis[ne]=1;
}
return ;
}
signed main(){
int n;
int be;
input(n,be);
fer(i,0,n-1){
fer(j,0,n-1){
input(w[i][j]);
}
}
dijistra(n,be);
for(int i=0;i<n;i++){
if(i==be){
continue;
}
else{
cout<<dist[i]<<" ";
}
}
}问题 E: 算法7-16：弗洛伊德最短路径算法
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
int mat[500][500];
int dis[500][500];
signed main(){
int n;
cin>>n;
memset(dis,0x3f,sizeof dis);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
input(mat[i][j]);
if(mat[i][j]!=0)
dis[i][j]=mat[i][j];
}
}
for(int i=0;i<n;i++)
dis[i][i]=0;
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<dis[i][j]<<" ";
}
cout<<'\n';
}
}问题 F: 图的最短路径-Floyd算法输出最短路径包含的边
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
int dij[101][101];
int path[101][101];
int a[101][101];
signed main(){
int n;
input(n);
fer(i,0,n-1)
fer(j,0,n-1){
int x,y;
input(x,y);
if(x!=-1){
dij[i][j] = x;
path[i][j] = y;
}
}
int x,y;
input(x,y);
int p = path[x][y];
stack<int>s;
s.push(y);
while (p!=x)
{
s.push(p);
p = path[x][p];
}
s.push(x);
cout<<dij[x][y]<<'\n';
while(s.size()){
auto t=s.top();
cout<<t<<" ";
s.pop();
}
}版权声明：本文为m0_61735576原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。