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

目录

今日知识点：

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

Job Hunt S

思路： 

最小花费

思路： 

朋友

思路： 

Job Hunt S

思路： 

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

所以每座城市都可以赚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;
}

最小花费

思路： 

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

#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]);
}

朋友

思路： 

并查集，找祖宗是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)]);
}