当前位置: 首页 > news >正文

图论刷题记录

  • P8186 [USACO22FEB] Redistributing Gifts S

Floyd 传递闭包模板。

首先对于每只奶牛,先看它和那些比在它目前手中礼物要珍贵的礼物的主人能否交换,然后做一遍传递闭包,最后对于每只奶牛直接找排名最靠前并且能与自己原本手中礼物互换的礼物。

直接用 Floyd 是 \(O(n^3)\) 的,我用的是 bitset 优化,优化到了 \(O(\frac{n^3}{w})\)

代码:

#include<bits/stdc++.h>
using namespace std;
int a[505][505];
bitset<505>f[505];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){cin >> a[i][j];}}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){f[i][a[i][j]] = 1;if(a[i][j] == i){break;}}}for(int j = 1;j<=n;j++){for(int i = 1;i<=n;i++){if(f[i][j]){f[i]|=f[j];}}}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(f[i][a[i][j]]&&f[a[i][j]][i]){cout << a[i][j] << '\n';break;}}}return 0;
}
  • P9126 [USACO23FEB] Moo Route II S

SPFA……它没死!!!

首先很容易想到朴素的 SPFA,但是复杂度是 \(O(nm)\) 的。很容易想到 SPFA 被卡的地方就是每条边无法保证只被遍历 \(1\) 次,所以……如何让它只被遍历 \(1\) 次?首先,你要知道,不管你到 \(i\) 的时间有多早,你都是在同一时刻到达另一个 \(j\),很显然,只需将图中的所有点的联通的点按照它起飞的时间降序排序,那么对于后面再访问只需访问前面没法访问的进行尝试即可,你会发现这样每条边只会遍历一次,所以复杂度变成了 \(O(n+m)\)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int vis[N];
int a[N];
int d[N];
int last[N];
struct node
{int x;int b;int e;
};
vector<node>e[N];
int q[N];
int cmp(node x,node y)
{return x.b>y.b;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin >> n >> m;for(int i = 1;i<=m;++i){int c,r,d,s;cin >> c >> r >> d >> s;e[c].push_back({d,r,s});}for(int i = 1;i<=n;++i){cin >> a[i];}a[1] = 0;for(int i = 1;i<=n;++i){sort(e[i].begin(),e[i].end(),cmp);}memset(d,0x3f,sizeof(d));int h = 1,t = 0;q[++t] = 1;d[1] = 0;vis[1] = 1;while(h<=t){int x = q[h];vis[x] = 0;++h;for(int _ = last[x];_<e[x].size();++_){int v = e[x][_].x,b = e[x][_].b,ee = e[x][_].e;if(b<d[x]+a[x]){break;}if(ee<d[v]){d[v] = ee;if(!vis[v]){vis[v] = 1;q[++t] = v;}}}}for(int i = 1;i<=n;++i){cout << (d[i] == d[0]?-1:d[i]) << '\n';}return 0;
}
  • P12026 [USACO25OPEN] Compatible Pairs S

一眼图论建模。

首先,当 \(d_i \le a\) 那么就可以让 \(i\)\(a-d_i\) 所在的编号连边,然后 \(b\) 也是同理,特判 \(a = b\) 的情况。然后建好边之后很显然发现这是一条可能有自环的链,最优做法就是从链的两端向里回流,很显然拓扑轻松搞定。

代码(要处理自环):

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
map<int,int>mp;
int w[N],d[N];
int chu[N];
int q[N];
vector<int>e[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,a,b;cin >> n >> a >> b;for(int i = 1;i<=n;++i){cin >> w[i] >> d[i];mp[d[i]] = i;}for(int i = 1;i<=n;++i){auto it = mp.find(a-d[i]);if(d[i]<=a&&it!=mp.end()){++chu[i];e[i].push_back(it->second);}if(a == b){continue;}it = mp.find(b-d[i]);if(d[i]<=b&&it!=mp.end()){++chu[i];e[i].push_back(it->second);}}int h = 1,t = 0;for(int i = 1;i<=n;i++){if(chu[i] == 1){q[++t] = i;	}}long long ans = 0;while(h<=t){int x = q[h];++h;for(int v:e[x]){if(v == x){ans+=w[v]>>1;w[v] = w[v]&1;}else if(w[v]){int cnt = min(w[x],w[v]);w[x]-=cnt;w[v]-=cnt;ans+=cnt;q[++t] = v;}}}cout << ans;return 0;
}
  • P12649 [KOI 2024 Round 2] 收集彩球

妙妙图论建模。

首先考虑将每个盒子上面的球的颜色向下面的球的颜色连一条有向边,然后会发现会形成若干个连通块,任意连通块互不影响,所以只看单个连通块如何处理,先判断无解,其实如果颜色中两个球都在各自盒子的上方的颜色数超过 \(1\),那么无解,显然是对的,因为挪动的情况只有空或者颜色相同,但很显然不可能颜色相同,空的话只能允许挪动一次,很明显要挪动的不止一次,所以无解。考虑如何算最小挪动次数,首先对于某个颜色,把这个颜色对应的两个球都拿上来,解放下面的球,花费 \(2\),然后将被解放的球挪动到与其颜色相同的球的上面,花费 \(cnt-1\),总共 \(2+(cnt-1) = cnt+1\)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int>e[N];
int ru[N];
int cnt;
int num;
int vis[N];
void dfs(int x)
{for(int v:e[x]){if(!vis[v]){++cnt;num+=ru[v] == 0;vis[v] = 1;dfs(v);}}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;for(int i = 1;i<=n;++i){int x,y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);++ru[y];}int ans = 0;for(int i = 1;i<=n;++i){if(!vis[i]){vis[i] = 1;cnt = 1;num = ru[i] == 0;dfs(i);if(num>1){cout << -1 << '\n';return 0;}if(cnt!=1){ans+=cnt+1;}}}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=36060

相关文章:

  • 「LG6596-How Many of Them」题解
  • 骗我呢
  • 手写体识别
  • 你好,我是肆闲:C语言的学习,成长与分享旅程
  • AGC 合集 1.0
  • 20231302邱之钊密码系统设计实验一第二
  • 深入BERT内核:用数学解密掩码语言模型的工作原理
  • ZR 2025 NOIP 二十连测 Day 6
  • 20251021
  • [论文笔记] Precision-Guided Context Sensitivity for Pointer Analysis
  • 英语_备忘_疑难
  • 数学题刷题记录(数学、数论、组合数学)
  • 朋友圈文案不会写?这个AI指令可能帮得上忙
  • 「JOISC2020-掃除」题解
  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​
  • 题解:P12525 [Aboi Round 1] 私は雨
  • 完整教程:罗技G102有线鼠标自己维修教程
  • 挖矿-学校挖矿排查