彼瞄 发表于 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

感谢分享，学习下。
页: [1]
查看完整版本: 图论刷题记录