Week 9 图论

P5318 【深基18.例3】查找文献

• 思路：用vector存单向图，排序，深搜光搜

• 注意：“如果有很多篇文章可以参阅，请先看编号较小的那篇”，需要排序（按终点由小到大排列，终点相同则起点有小到大

  #include<bits/stdc++.h> 
  using namespace std;  
  struct edge{    
  	int u,v;
  }; 
  vector <int> e[100001]; 
  vector <edge> s;
  bool vis1[100001]={0},vis2[100001]={0};
  bool cmp(edge x,edge y)
  {
  	if(x.v==y.v)
  	return x.u<y.u;
  	else return x.v<y.v;
  }
  void dfs(int x)//深搜 
  {
  	vis1[x]=1;
  	cout<<x<<" ";
  	for(int i=0;i<e[x].size();i++){
  		int point=s[e[x][i]].v;
  		if(!vis1[point]){
  			dfs(point);
  		}
  	}
  }
  void bfs(int x) //广搜 
  {  
  	queue <int> q;
  	q.push(x);
  	cout<<x<<" ";
  	vis2[x]=1;
  	while(!q.empty()){
  		int fro=q.front();
  		for(int i=0;i<e[fro].size();i++){
  			int point=s[e[fro][i]].v;
  			if(!vis2[point]){
  				q.push(point); 
  				cout<<point<<" ";
  				vis2[point]=1;
  			}
  		}
  		q.pop();
  	}
  }
  int main(){
  	int n,m; 
  	cin>>n>>m; 
  	for(int i=0;i<m;i++){
  		int x,y;
  		cin>>x>>y;
  		s.push_back((edge){x,y});   
  	}
  	sort(s.begin(),s.end(),cmp); 
  	for(int i=0;i<m;i++)   
  		e[s[i].u].push_back(i); 
  	dfs(1);  
  	cout<<endl;
  	bfs(1); 
  }
  

U80592 【模板】floyd

• 模板题直接套floyd就行

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const long long t=998244354;
int n,m;
long long f[505][505];
int main()
{
    long long u,v,w;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=INF;
            f[i][i]=0;
        }
    }
    
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        f[u][v]=min(w,f[u][v]);
        f[v][u]=min(w,f[v][u]);
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
            }
        }
    }
    long long ans;
    for(int i=1;i<=n;i++)
    {
        ans=0;
        for(int j=1;j<=n;j++)
        {
            if(f[i][j]!=INF)
            {ans=(ans+f[i][j])%t;}
        }
        cout<<ans<<endl;
    }
}

P4779 【模板】单源最短路径（标准版）

• 模板题，dijkstra算法

#include <bits/stdc++.h>
using namespace std;

struct edge
{
	int to,w;
	edge(int a,int b){
		to=a;
		w=b;
	}
};

struct node 
{
	int id,s;
	node(int a,int b){
		id=a;
		s=b;
	}
	bool operator >(const node c) const{
		return s>c.s;
	}
};

int n,m,be;
vector <edge> e[100005];
int dis[100005];
bool vis[100005];

void dijkstra(int be)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[be]=0;
	priority_queue <node,vector<node>, greater<node> > Q;
	Q.push(node(be,0));
	while(!Q.empty())
	{
		node nd=Q.top();
		Q.pop();
		if(vis[nd.id])
			continue;
		vis[nd.id]=true;
		for(int i=0;i<e[nd.id].size();++i)
		{
			edge y=e[nd.id][i];
			if(vis[y.to])
				continue;
			if(dis[y.to]>y.w+nd.s) 
			{
				dis[y.to]=y.w+nd.s;
				Q.push(node(y.to,dis[y.to]));
			}
		}
	}
}

int main()
{
	cin>>n>>m>>be;
	for(int i=1;i<=m;++i)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c); 
		e[a].push_back(edge(b,c));
	}
	dijkstra(be);
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dis[i]);
	}
	return 0;
}