图论模板
程序员文章站
2022-05-22 14:35:50
...
一、最小生成树
(1) prim + 邻接矩阵
int prim(int s)
{
int sum = 0;
//memset(vis,false,sizeof(vis));
memset(dis,INF,sizeof(dis));
dis[s] = 0;
for(int i = 0; i < n; ++i){
dis[i] = map[s][i];
}
//vis[s] = true;
int cur;
for(int i = 0; i < n; ++i){
if(s == i) continue;
int min_dis = INF;
for(int j = 0; j < n; ++j){//寻找MST外距离MST最近的点
if(dis[j] != 0 && dis[j] < min_dis){
min_dis = dis[j];
cur = j;
}
}
dis[cur] = 0;
sum += min_dis;
for(int v = 0; v < n; ++v){//更新与当前新加入点cur临接点到生成树的距离
if(dis[v] != 0 && map[cur][v] < dis[v]){
dis[v] = map[cur][v];
}
}
}
printf("%d\n",sum);
}
(2)prim + 邻接表
#include<bits/stdc++.h>
using namespace std;
const int MAXM = 50000+5;
const int MAXN = 1000+5;
bool mark[MAXN];
struct Edge{
int to,w;
Edge(int pt,int pw){
to = pt; w = pw;
}
bool operator<(const Edge o)const{
return w > o.w;
}
};
int n,m,cnt;
vector<Edge> adj[MAXN];
priority_queue<Edge> pq;
void vis(int cur){
mark[cur] = true;
++cnt;
for(int i = 0; i < adj[cur].size(); ++i){
Edge e = adj[cur][i];
if(!mark[e.to]){
pq.push(e);
}
}
}
void prim(int s)
{
cnt = 1;
int sum = 0;
memset(mark,false,sizeof(mark));
mark[s] = true;
for(int i = 0; i < adj[s].size(); ++i){
pq.push((Edge)adj[s][i]);
}
int to;
while(cnt < n){
Edge e = pq.top();
pq.pop();
to = e.to;
if(mark[to]) continue;
sum += e.w;
vis(to);
}
printf("%d\n",sum);
}
int main()
{
cin >> n >> m;
int f,t,w;
for(int i = 0; i < m; ++i){
cin >> f >> t >> w;
adj[f].push_back(Edge(t,w));
adj[t].push_back(Edge(f,w));
}
prim(1);
return 0;
}
(3)kruskal + 优先队列 + 并查集
#include<stdio.h>
#include<algorithm>
#define MAX 105
using namespace std;
int n, m,tol;
struct Edge{
int from,to,w;
int next;
};
bool cmp(const Edge a, const Edge b){
return a.w < b.w;
}
int id[MAX];
int head[MAX];
Edge edges[MAX*MAX];
int find(int p){
if(id[p] == p)
return p;
else return id[p] = find(id[p]);
}
void addEdge(int from, int to, int w)
{
edges[tol].from = from;
edges[tol].to = to;
edges[tol].w = w;
edges[tol].next = head[from];
head[from] = tol++;
}
int main()
{
int from,to,w;
while(scanf("%d%d",&m,&n) == 2 && n!=0 && m != 0){
tol = 0;
int sum = 0;
int cop = n;
for(int i = 1; i <= n; ++i){
id[i] = i;
head[i] = -1;
}
for(int i = 0; i < m; ++i){
scanf("%d%d%d",&from,&to,&w);
addEdge(from,to,w);
}
sort(edges,edges+m,cmp);//排序
for(int i = 0; i < m; ++i){
int p = find(edges[i].from);
int q = find(edges[i].to);
if(p == q)
continue;
id[p] = q;
sum += edges[i].w;
--cop;
}
if(cop > 1){
printf("?\n");
}
else{
printf("%d\n",sum);
}
}
return 0;
}
kruskal(2)
#include<bits/stdc++.h>
using namespace std;
const int MAXM = 50000+5;
const int MAXN = 1000+5;
int id[MAXN];
int n,m;
struct Node{
int f,t,w;
bool operator<(const Node o)const{
return w < o.w;
}
}nodes[MAXM];
int find(int p){
if(p == id[p])
return p;
else return id[p] = find(id[p]);
}
int main()
{
cin >> n >> m;
for(int i = 0; i <= n; ++i)//这个初始化 不能放在输入m,n之前 否则错误 也不知道为啥 醉了
id[i] = i;
for(int i = 0; i < m; ++i){
cin >> nodes[i].f >> nodes[i].t >> nodes[i].w;
}
sort(nodes,nodes+m);
int sum = 0;
for(int i = 0; i < m; ++i){
Node tmp = nodes[i];
int p = find(tmp.f);
int q = find(tmp.t);
if(p == q) continue;
id[p] = q;
sum += tmp.w;
}
printf("%d\n",sum);
return 0;
}
二、最短路径
(1)dijkstra + 优先队列+模拟邻接表
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXM = 10005;
struct Edge{
int to, w;
Edge(int pto, int pw){
to = pto;
w = pw;
}
bool operator < (const Edge o) const{
return w > o.w;
}
};
long long dis[MAXN];
bool vis[MAXN];
vector<Edge> adj[MAXN];
int n, m;
int dijkstra()
{
memset(dis,INF,sizeof(dis));
memset(vis,false,sizeof(vis));
priority_queue<Edge> pq;
dis[1] = 0;
pq.push(Edge(1,0));
while(!pq.empty()){
Edge tmp = pq.top();
int cur = tmp.to;
if(cur == n){
return dis[n];
}
vis[cur] = true;
pq.pop();
for(int i = 0; i < adj[cur].size(); ++i){
Edge e = adj[cur][i];
if(!vis[e.to]){
if(dis[e.to] > dis[cur] + e.w){
dis[e.to] = dis[cur] + e.w;
pq.push(Edge(e.to,dis[e.to]));
}
}
}
}
return 0;
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&m) && n!=0 && m!=0){
for(int i = 1; i <= n; ++i){
adj[i].clear();
}
for(int i = 1; i <= m; ++i){
scanf("%d%d%d",&a,&b,&c);
adj[a].push_back(Edge(b,c));
adj[b].push_back(Edge(a,c));
}
int ans = dijkstra();
printf("%d\n",ans);
}
return 0;
}
三、tarjan算法
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 1000+5;
int low[N];
int dfn[N];
bool vis[N];
vector<int> adj[N];
int index;
bool flag[N];
bool mark[N][N];
int n,m,root;
/*
求割点
*/
void tarjan(int cur, int fa)
{
int child = 0;
low[cur] = dfn[cur] = ++index;
vis[cur] = true;
for(int i = 0; i < adj[cur].size(); ++i){
int v = adj[cur][i];
if(!vis[v]){
++child;
tarjan(v,cur);
low[cur] = min(low[cur],low[v]);
if(cur != root && low[v] >= dfn[cur]){ //注意这里是 low[v] 子节点不能回到更早 不是low[cur]
flag[cur] = true;
}
if(cur == root && child > 1){
flag[cur] = true;
}
}
else if(fa != v){
low[cur] = min(low[cur],dfn[v]);
}
}
}
/*
求割边
*/
void tarjan(int cur, int fa)
{
low[cur] = dfn[cur] = ++index;
vis[cur] = true;
for(int i = 0; i < adj[cur].size(); ++i){
int v = adj[cur][i];
if(!vis[v]){
tarjan(v,cur);
low[cur] = min(low[cur],low[v]);
if(low[v] > dfn[cur]) {
//printf("%d - %d\n",cur,v);
mark[cur][v] = true;
}
}
else if(fa != v){
low[cur] = min(low[cur],dfn[v]);
}
}
}
int main()
{
memset(flag,false,sizeof(flag));
index = 0;
scanf("%d%d",&n,&m);
root = 1;
int a,b;
for(int i = 0; i < m; ++i){
scanf("%d%d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
tarjan(1,1);
for(int i = 0; i <= n; ++i){
if(flag[i]){
printf("%d",i);
}
}
return 0;
}
上一篇: 图论模板
推荐阅读
-
OpenCV 模板匹配去重
-
ecshop怎样套用新的模板,新的模板文件都是html的
-
前端笔记之NodeJS(三)Express&ejs模板引擎&请求识别
-
Yii2的相关学习记录,后台模板和gii(三) - 漫游云巅
-
手机模板_苹果风格 iOS7 X3_X3.1版源码
-
ThinkPHP模板输出display用法分析,thinkphpdisplay_PHP教程
-
在Yii框架中使用PHP模板引擎Twig的例子
-
thinkphp中include传参有缓存,模板缓存清理
-
Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?(图论+连通块+bfs)
-
PHP.MVC的模板标签系统(三)