2025夏图论小测3考试总结
比赛情况
| 题目 | 分数 | 总分 |
|---|---|---|
| [USACO3.2] 香甜的黄油 Sweet Butter | 80分 | 380分 |
| 【模板】负环 | 10分 | |
| [USACO09OPEN] Hide and Seek S | 10分 | |
| 营救 | 100分 | |
| [NOIP 2017 提高组] 奶酪 | 80分 | |
| 最小花费 | 0分 | |
| 道路重建 | 100分 |
题目总结
[USACO3.2] 香甜的黄油 Sweet Butter
错误原因
数组开小了，眼瞎看成500了
正确思路
题目说从任意一点到某个点i的最短距离之和要最小，那么我们就可以有两种方法：\ 方法一：floyd 跑一遍floyd，枚举终点i，打擂台求各点到点i的最短距离。\ 方法二：dijkstra 因为这题是无向边，所以我们可以枚举终点i然后跑以i为起点的dijkstra最后以同样的方法求和。
AC Code(核心代码)
floyd
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
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
#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
#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
#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
#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
#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
#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;
}总结
这次考试有很多细节问题，之后在写完一个代码后，要检查几次，自己造几个数据测试，不能再这样大意。