图论刷题记录

• P8186 [USACO22FEB] Redistributing Gifts S
  

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

过来提前占个楼

这个有用。

感谢分享

感谢分享，学习下。