0412备战蓝桥杯，图论复习

1.朴素dijkstra

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
const int N = 510; 

int n,m;
int g[N][N],dist[N];
bool st[N];

int dij(){

memset(dist,0x3f,sizeof dist);
dist[1] = 0;

for(int i=0;i<n;i++){//n次迭代 
int t = -1;
for(int j=1;j<=n;j++)
if(!st[j] && (t == -1 || dist[j] < dist[t])) 
t=j;
st[t] = true;
for(int j=1;j<=n;j++){
dist[j] = min(dist[j],dist[t]+g[t][j]);
} 
}

if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);

for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(g[a][b],c);
}

int t = dij();
cout<<t<<endl;
return 0;
}

2.floyd：初始化自己到自己是0

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
const int N = 210; 

int n,m,k;
int e[N][N];
int st[N];

void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
e[i][j] = min(e[i][j],e[i][k]+e[k][j]);
}
}
}
return ;
}


int main(){
cin>>n>>m>>k;
//memset(e,0x3f,sizeof e);
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i==j) e[i][j] = 0;
        else e[i][j] = 0x3f3f3f3f;
    }
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
e[a][b] = min(e[a][b],c);
}

floyd();

while(k--){
int x,y;
cin>>x>>y;

if(e[x][y] > 0x3f3f3f3f/2) cout<<"impossible"<<endl;
else cout<<e[x][y]<<endl;
}
return 0;
} 

3.prim：点到集合的距离

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
const int N = 510; 

int e[N][N];
int st[N];
int dist[N];//点到集合的距离 
int n,m;
int res;
int cnt;

int prim(){
memset(dist,0x3f,sizeof dist);

for(int i=0;i<n;i++)//n次迭代
{
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[j]<dist[t])){
t=j;
}
}
if(i && dist[t] == 0x3f3f3f3f){
return 0x3f3f3f3f;//一定要返回无穷大1，不然-1也有可能是答案
}
if(i) res+=dist[t];
st[t] = true;

/*st[t] = true;
cnt++;
res+=dist[t];
*/
for(int j=1;j<=n;j++){
//用t更新点到集合的距离
dist[j] = min(dist[j], e[t][j]); 
}

} 

return res;
}
int main()
{
cin>>n>>m;
memset(e,0x3f,sizeof e);
while(m--){
int u,v,w;
cin>>u>>v>>w;
if(u==v) continue;
e[u][v] = e[v][u] = min(e[v][u],w);
}

if(prim() == 0x3f3f3f3f) cout<<"impossible"<<endl;
else cout<<prim()<<endl;
return 0;
} 
 

4.kruskal：选取最小边进入集合，注意并查集p[x] = find(p[x])

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
const int N = 200010; 
//kruskal从最短边加入集合
int p[N];
int n,m;
struct node{
int u,v,w;
}; 
node e[N];
int res,cnt;

bool cmp(node aa,node bb){
return aa.w < bb.w;
}

int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;

for(int i=1;i<=m;i++)
{
int u,v,w;
//if(u==v) continue;
cin>>u>>v>>w;
e[i] = {u,v,w};
}
sort(e+1,e+m+1,cmp);
//枚举每条边 
for(int i=1;i<=m;i++){
int u=e[i].u;
int v=e[i].v;
int w=e[i].w;
u=find(u);
v=find(v);
if(u!=v){
//如果不在一个连通块
res += w;
cnt++;
p[u] = v;//加入集合 
} 
}
if(cnt<n-1) cout<<"impossible"<<endl;
else cout<<res<<endl; 
return 0;
} 

原文地址：https://blog.csdn.net/2401_82736456/article/details/137688612

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！