彼瞄 发表于 2025-10-21 21:25:01

图论刷题记录


[*]P8186 Redistributing Gifts S
Floyd 传递闭包模板。
首先对于每只奶牛，先看它和那些比在它目前手中礼物要珍贵的礼物的主人能否交换，然后做一遍传递闭包，最后对于每只奶牛直接找排名最靠前并且能与自己原本手中礼物互换的礼物。
直接用 Floyd 是 \(O(n^3)\) 的，我用的是 bitset 优化，优化到了 \(O(\frac{n^3}{w})\)。
代码：
#includeusing namespace std;int a;bitsetf;signed main(){        ios::sync_with_stdio(0);        cin.tie(0);        cout.tie(0);        int n;        cin >> n;        for(int i = 1;i a;                }        }        for(int i = 1;i r >> d >> s;                e.push_back({d,r,s});        }        for(int i = 1;i> a;        }        a = 0;        for(int i = 1;i> d;                mp] = i;        }        for(int i = 1;i n;        for(int i = 1;i> x >> y;                e.push_back(y);                e.push_back(x);                ++ru;        }        int ans = 0;        for(int i = 1;i1)                        {                                cout

骆贵 发表于 2025-10-24 17:13:13

过来提前占个楼

钨哄魁 发表于 2025-10-25 00:52:56

这个有用。

暴灵珊 发表于 2025-12-3 22:11:11

感谢分享

丘娅楠 发表于 2025-12-4 16:59:53

感谢分享，学习下。

猷浮 发表于 2025-12-23 07:35:40

yyds。多谢分享

镝赋洧 发表于 2025-12-31 00:35:28

感谢分享

劳暄美 发表于 2026-1-14 05:38:00

鼓励转贴优秀软件安全工具和文档！

骆熙华 发表于 2026-1-14 06:27:48

感谢分享，下载保存了，貌似很强大

请蒂 发表于 2026-1-15 04:30:33

yyds。多谢分享

司寇涵涵 发表于 2026-1-15 21:42:48

收藏一下   不知道什么时候能用到

纪音悦 发表于 2026-1-18 09:23:18

yyds。多谢分享

嗣伐 发表于 2026-1-19 10:46:28

感谢，下载保存了

枢覆引 发表于 2026-1-21 16:37:52

感谢分享，下载保存了，貌似很强大

芮梦月 发表于 2026-1-22 19:56:30

分享、互助 让互联网精神温暖你我

站竣凰 发表于 2026-1-28 04:02:27

谢谢分享，试用一下

巫雪艷 发表于 2026-2-1 14:42:56

东西不错很实用谢谢分享

司寇涵涵 发表于 2026-2-1 18:51:15

谢谢分享，辛苦了

酝垓 发表于 2026-2-2 10:42:15

过来提前占个楼

慕疼 发表于 2026-2-7 23:00:39

用心讨论，共获提升！
页: [1] 2 3
查看完整版本: 图论刷题记录