专栏文章

2025夏图论小测3考试总结

ccaizimo
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioyt08u
此快照首次捕获于
2025/12/03 03:22
3 个月前
此快照最后确认于
2025/12/03 03:22
3 个月前
查看原文

比赛情况

题目分数总分
[USACO3.2] 香甜的黄油 Sweet Butter80分380分
【模板】负环10分
[USACO09OPEN] Hide and Seek S10分
营救100分
[NOIP 2017 提高组] 奶酪80分
最小花费0分
道路重建100分

题目总结

[USACO3.2] 香甜的黄油 Sweet Butter

错误原因

数组开小了，眼瞎看成500了

正确思路

题目说从任意一点到某个点i的最短距离之和要最小，那么我们就可以有两种方法：
方法一：floyd 跑一遍floyd，枚举终点i，打擂台求各点到点i的最短距离。
方法二：dijkstra 因为这题是无向边，所以我们可以枚举终点i然后跑以i为起点的dijkstra最后以同样的方法求和。

AC Code(核心代码)

floyd

CPP
floyd();
ll minn=INT_MAX;
for(int i=1;i<=n;i++){
	ll ans=0;
	for(int j=1;j<=n;j++){
		ans=ans+1ll*dp[j][i]*a[j];
	}
	minn=min(minn,ans);
}
cout<<minn;

dijkstra

CPP
ll sum=LONG_LONG_MAX;
for(int i=1;i<=n;i++){
  dijkstra(i);	
  ll ans=0;
  for(int j=1;j<=n;j++){
      ans=ans+1ll*dis[j]*a[j];
  }
  sum=min(sum,ans);
}
cout<<sum;

【模板】负环

错误原因

1.初始化dis数组时，用for没有写0x3f3f3f3f，而是0x3f 2.t组数据没有清空vector

正确思路

本题是一个判负环的模版题，我们利用最短路最多只有总边数-1条边的特性，在spfa中维护当前边数，一边维护一遍判断是否大于总边数-1，就可以判断出有没有最短路。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y,w;
};
int n,m,dis[N],vis[N],cnt[N];
vector<node> g[N];
bool spfa(int s){
	queue<int> q;
	for(int i=1;i<=n;i++){
		dis[i]=0x3f3f3f3f;
		vis[i]=cnt[i]=0;
	}
	dis[s]=0;
	q.push(s);
	vis[s]=1;
	cnt[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y,w=g[x][i].w;
			if(dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				cnt[y]=cnt[x]+1;
				if(cnt[y]>n-1) return 1;
				if(vis[y]==0){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return 0;
}
int main(){
//	freopen("B.in","r",stdin);
//	freopen("B.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear();
		for(int i=1;i<=m;i++){
			int x,y,w; cin>>x>>y>>w;
			g[x].push_back({y,w});
			if(w>=0) g[y].push_back({x,w});
		}
		if(spfa(1)) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

[USACO09OPEN] Hide and Seek S

错误原因

审题不仔细，把要求求的东西搞混淆了，导致答案错误

正确思路

这道题题目有点绕，但要求的东西十分简单，题目要我们求：以1为起点的最短路的最大值以及他的编号and有多少个与他距离一样的最短路。
看到起点一定，我们就想到dijkstra，所以我们先求一个1为起点的dijkstra，然后打擂台求出最大值，最后循环找出与他一样的最短路

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y,w;
	bool operator < (const node & tmp) const 
	{
		return w>tmp.w;
	}
};
int n,m,dis[N],vis[N];
vector<node> g[N];
void dijkstra(int s){
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=0;
	q.push({s,dis[s]});
	while(!q.empty()){
		int x=q.top().y;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y,w=g[x][i].w;
			if(dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				q.push({y,dis[y]});
			}
		}
	}
}
int main(){
//	freopen("C.in","r",stdin);
//	freopen("C.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		g[x].push_back({y,1});
		g[y].push_back({x,1});
	}
	dijkstra(1);
	int maxn=-1,mi;
	for(int i=1;i<=n;i++){
		if(maxn<dis[i]){
            maxn=dis[i];
            mi=i;
        }
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(dis[i]==maxn) ans++;
    }
	cout<<mi<<' '<<maxn<<' '<<ans;
	return 0;
}

营救

正确思路

这题要我们求一条路径中最大的权值最小，我们学习过用floyd求最大值最小，但这题10000的数据肯定不能用那个神奇的三重循环，所以我们可以在dijkstra中用floyd的思路，把每次松弛的条件改成判断最大值，这样就可以达到的floyd一样的效果。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y,w;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
int n,m,s,t,dis[N],vis[N];
vector<node> g[N];
void dijkstra(int s){
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=0;
	q.push({s,dis[s]});
	while(!q.empty()){
		int x=q.top().y;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y,w=g[x][i].w;
			if(max(dis[x],w)<dis[y]){//用floyd的思路修改
				dis[y]=min(dis[y],max(dis[x],w));
				q.push({y,dis[y]});
			}
		}
	}
}
int main(){
//	freopen("D.in","r",stdin);
//	freopen("D.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int x,y,w; cin>>x>>y>>w;
		g[x].push_back({y,w});
		g[y].push_back({x,w});
	}
	dijkstra(s);
	cout<<dis[t];
	return 0;
}

[NOIP 2017 提高组] 奶酪

错误原因

细节问题，数组和其他函数里有的数组没有定义成double类型，导致答案错误。

正确思路

本题是一道十分经典的并查集的题目，题目说，给定n球点，每条边之间如果距离小于他们的球心距，那么就能联通，问能否从下表面走到上表面。
既然这道题只是求能否联通，那么我们就可以用并查集来解决。首先枚举两个球，接着判断他们的距离，如果小于等于球心距，那么就unionn(i,j)，最后判断find(0)和find(n+1)，也就是上下表面是否在同一个集合就行了。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
double x[N],y[N],z[N],fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y){
		fa[x]=y;
	}
	return ;
}
double dist(int i,int j){
	double p1=abs(x[i]-x[j])*abs(x[i]-x[j]);
	double p2=abs(y[i]-y[j])*abs(y[i]-y[j]);
	double p3=abs(z[i]-z[j])*abs(z[i]-z[j]);
    double q=sqrt(p1+p2+p3);
	return q;
}
void solve(){
	double n,h,r; cin>>n>>h>>r;
	for(int i=0;i<=n+1;i++) fa[i]=i;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>z[i];
		if(z[i]<=r) unionn(i,0);
		if(z[i]+r>=h) unionn(i,n+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(dist(i,j)<=2*r) unionn(i,j);
		}
	}
	if(find(0)==find(n+1)) cout<<"Yes\n";
	else cout<<"No\n";
}
int main(){
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

最小花费

错误原因

没有思考清楚，在定义优先队列时，没有修改重载运算符，导致全wa。

正确思路

这道题要我们求一个数，使他在乘以一些数后等于100，我们要求出这个数最小是多少。 看到这道题，我们想想就会发现我们可以反过来求，求他的最大到手率，在最后再用100除以他就可以了

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y;
	double w;
	bool operator < (const node & tmp) const
	{
		return w < tmp.w;
	}
};
double n,m,dis[N],vis[N];
vector<node> g[N];
void dijkstra(int s){
	priority_queue<node> q;
    for(int i=1;i<=n;i++) dis[i]=-1e9;
	memset(vis,0,sizeof vis);
	dis[s]=1;
	q.push({s,dis[s]});
	while(!q.empty()){
		ll x=q.top().y;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y;
			double w=g[x][i].w;
			if(dis[x]*w>dis[y]){
				dis[y]=dis[x]*w;
				q.push({y,dis[y]});
			}
		}
	}
}
int main(){
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,w; cin>>x>>y>>w;
		double z=(100-w)/100.0;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	int a,b; cin>>a>>b;
	dijkstra(a);
	cout<<fixed<<setprecision(8)<<100.0/dis[b];
	return 0;
}

道路重建

正确思路

这道题看起来十分简单，但实际上确实十分简单有个坑，看上去只要我们求一个最短路，但是注意，我们跑最短路的时候只有在道路被损毁的时候才有边权，所以我们可以先把边权保存，在道路被损毁时在赋值，这样就得到了一张符合题目的图，接着再跑最短路就行了。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y,w;
	bool op;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
int n,m,dp[200][200],a[200][200];
vector<node> g[N];
int main(){
//	freopen("G.in","r",stdin);
//	freopen("G.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dp,0x3f,sizeof dp);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z; cin>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
		dp[x][y]=0;
		dp[y][x]=0;
	}
	int d; cin>>d;
	for(int i=1;i<=d;i++){
		int x,y; cin>>x>>y;
		dp[x][y]=a[x][y];
		dp[y][x]=a[y][x];
	}
	for(int i=1;i<=n;i++) dp[i][i]=0;
	int a,b; cin>>a>>b;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	cout<<dp[a][b];
	return 0;
}

总结

这次考试有很多细节问题，之后在写完一个代码后，要检查几次，自己造几个数据测试，不能再这样大意。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...