图论(week 9)

发布于 2023-05-12  125 次阅读


T1 查找文献 (dfs bfs模板题)

下附代码:

#include <bits/stdc++.h>
using namespace std;
const int maxx=1e6+5;
int n,m;
int vis[maxx];
vector<int> book[maxx];
queue<int> b;
void dfs(int x){
	if(vis[x]==1) return;
	vis[x]=1;
	cout<<x<<' ';
	for(int i=0;i<book[x].size();++i){
		dfs(book[x][i]);
	}
}
void bfs(){
	b.push(1);
	while(!b.empty()){
		int x=b.front();
		b.pop();
		cout<<x<<' ';
		vis[x]=1;
		for(int i=0;i<book[x].size();++i){
			int next=book[x][i];
			if(vis[next]==1) continue;
			else{
				b.push(next);
				vis[next]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int f,e;
		cin>>f>>e;
		book[f].push_back(e);
	}
	for(int i=1;i<=n;i++){
		sort(book[i].begin(),book[i].end());
	}//排序n种资料
	dfs(1);
	cout<<endl;
	memset(vis,0,sizeof(vis));
	bfs();
	return 0;
}

T2 Floyd(最短路n^3模板题)

floyd比较短,本质上是一种dp算法。时间复杂度为 n^3,n<10^3内的数据可以用。floyd适用性也很高,遍历所有点所以可以做到一些生成树算法的功能。

下附代码:

#include <iostream>
#include <cstring>
using namespace std;
const long long int mod = 998244354;
const long long int INF=25e13+500;
int n,m;
long long int ans;
long long int map[505][505];
int main(){
	for(int i=1;i<=503;i++)
	for(int l=1;l<=503;l++){
		if(i==l) map[i][l]=0;
		else map[i][l]=INF;
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		if(map[s][e]!=0&&map[s][e]>v){
			map[s][e]=v;
			map[e][s]=v;
		}
		//无向图。
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int l=1;l<=n;l++){
				if(i==l) continue;
				if(map[k][l]<INF&&map[i][k]<INF&&map[i][l]>(map[k][l]+map[i][k]))
				map[i][l]=(map[k][l]+map[i][k]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=0;
		for(int l=1;l<=n;l++){
			ans+=map[i][l];
			ans%=mod;
		}
		cout<<ans%mod<<endl;
	}
	return 0;
}

T3 单源最短路径(标准版)

用dijkstra时要用堆来优化缩边过程的选点步骤,可以用优先队列来存放到各点的估计值。

各种存图方式,代码用了vector数组进行存图

下附代码:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf=2e9+5;
struct point{
	int end,len;
	bool operator < (const point a) const{
		return len < a.len;
	}//重载运算符
	bool operator > (const point a) const{
		return len > a.len;
	}
};
int n,m,st,cnt,now;
bool book[100005];
vector <point> a[100005];//最多1e5个点
priority_queue <point, vector<point>,greater<point> > dis;
int ans[100005];//存答案的数组。
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=100005;i++){
		ans[i]=inf;
	}
	ans[st]=0;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		a[s].push_back({e,v});
	}//vector存图
	dis.push({st,0});//存入起点
	while(!dis.empty()){
		point temp=dis.top();
		dis.pop();
		now=temp.end;
		//因为确定值不能重复更新(优先队列内仍可能存在
		//所以要加一个判断。
		if(!book[now]){
			book[now]=true;
			for(int i=0;i<a[now].size();i++){
				//遍历所有边 vector下标从0开始
				point x=a[now][i];
				int to=x.end;
				int v=x.len;
				//dijkstra核心代码
				if(ans[to]>ans[now]+v){
					ans[to]=ans[now]+v;
				//dijkstra核心代码
					if(!book[to]){
						//减少判断次数,去掉不影响算法正确性。
						dis.push({to,ans[to]});
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}