马上蓝桥杯了,为你带来几道图论题

admin2024-04-03  0

目录

今日知识点:

当边权和点权都有,常常会把点权转化为边权,然后统一去跑边

Job Hunt S

思路: 

最小花费

思路: 

朋友

思路: 


        

        

Job Hunt S

马上蓝桥杯了,为你带来几道图论题,第1张

马上蓝桥杯了,为你带来几道图论题,第2张

思路: 


本题的特点就是边权和点权都有,对于都有的情况我们常常会把点权转化为边权,然后统一去跑边。因为对于某点权来讲完全可以等价于其点周围边权都相等的一种特殊情况!

所以每座城市都可以赚d元,不就等价于周围点到这里的边权就是d元嘛,飞行边需要花费t,而一个城市又可以赚d,那么边权就是d-t,然后spfa跑最长路即可

#include <bits/stdc++.h>
using namespace std;
const int N=300,M=600;
int vis[N],ans,dis[N],head[N],tot,d,p,c,f,s;
struct node{int to,w,next;}e[M];
void add(int u,int v,int w){e[++tot]={v,w,head[u]};head[u]=tot;}
void spfa(int u){
	queue<int>q;
	q.push(u);vis[u]=1;
	while(!q.empty()){
		int cur=q.front();q.pop();vis[cur]=0;
		for(int i=head[cur];i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(dis[v]<dis[cur]+w){
				dis[v]=dis[cur]+w;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}
}
int main(){
	cin>>d>>p>>c>>f>>s;int u,v,w;
	for(int i=1;i<=p;i++){
		cin>>u>>v;
		add(u,v,d);
	}
	for(int i=1;i<=f;i++){
		cin>>u>>v>>w;
		add(u,v,d-w);
	}
	spfa(s);
	for(int i=1;i<=c;i++){
		ans=max(ans,dis[i]);
	}
	cout<<ans+d;
}

        

        

最小花费

马上蓝桥杯了,为你带来几道图论题,第3张

马上蓝桥杯了,为你带来几道图论题,第4张

思路: 

还是跑最长路,只不过是转移式子有所变化,

#include <bits/stdc++.h>
using namespace std;
const int N=2010,M=1e6+10;
int vis[N],n,m,tot,head[N];
double dis[N];
struct node {int to,w,next;}e[M];
void add(int u,int v,int w){e[++tot]={v,w,head[u]};head[u]=tot;}
void spfa(int s){
	queue<int>q;
	q.push(s);vis[s]=1;
	dis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(dis[v]<dis[u]*(100-w)/100.0){
				dis[v]=dis[u]*(100-w)/100.0;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	int a,b;cin>>a>>b;
	spfa(a);
	printf("%.8lf",100/dis[b]);
}

        

         

朋友

马上蓝桥杯了,为你带来几道图论题,第5张

马上蓝桥杯了,为你带来几道图论题,第6张

思路: 

并查集,找祖宗是find,别学我用fa

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10,M=2e5;
int n,m,p,q,fa[N],cnt[N];
int find(int u){
	if(u!=fa[u]) fa[u]=find(fa[u]);
	return fa[u];
}
void unity(int u,int v){
	int fu=find(u),fv=find(v);
	if(fu!=fv){//或者把判断过程写到主函数也行
		fa[fu]=fv;
		cnt[fv]+=cnt[fu];
	}
}
int main(){
	cin>>n>>m>>p>>q;int x,y;
	for(int i=1;i<=N;i++)fa[i]=i,cnt[i]=1;//记得对cnt初始化,不然一直是0
	for(int i=1;i<=p;i++){
		cin>>x>>y;
		unity(x,y);
	}
	for(int i=1;i<=q;i++){
		cin>>x>>y;x*=-1;y*=-1;
		unity(x+M,y+M);
	}
//	cout<<min(cnt[fa[1]],cnt[fa[1+M]]);//这个步骤花了我一下午调试
	cout<<min(cnt[find(1)],cnt[find(1+M)]);
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!