点分治分点(BFS)

科技前沿 • 2025-02-16 07:59 • 阅读 30

大家好，我是讯享网，很高兴认识大家。

D-点分治分点_牛客练习赛105 (nowcoder.com)

题意:

给定一个n个点, m 条带权的边的有向图，定义一条简单路径的low值为其路径上的边权的最小值，d(u, u)为从u到v所有简单路径的最大low值。注意，简单路径不能包含两个相同的点，故恒有d(u, u)=—1。
对于给定的s，u从1到n输出d(s, u)，如果没有任何一条简单路径则输出一1。
输入描述:
第一行三个正整数n, m,s(1 ≤n, m ≤105,1 ≤s≤n)。
后面m行，每行三个整数ui, o,w;(1 ≤ui,ui≤n,1≤u≤109)，分别代表一条从u;连向vi，权值为wi的边。注意，可能存在重边和自环。
输出描述:
输出一行，包含n个整数，第i个整数表示d(s,i)的值，如果没有任何一条简单路径则输出—1。

输入

5 7 1 1 2 3 1 3 4 2 3 5 2 5 1 3 4 1 5 4 3 3 5 9

讯享网

输出

讯享网-1 3 4 3 4

题解:

BFS,根据dis[j]存的是s的简单路径到j的low值,因为我们要求的是所以简单路径的的最大low值,所以要用优先队列把每次遍历最大的值放到队首,要用优先队列,

讯享网

在过程中,要把此时s到点i的最大简单路径的low值,与min(上一个点j到i的w,上一个点的所有简单路径的最大low值)比较

如果小于之前的说明此时的dis[i]不是s到i的所有简单路径的最大low值,所以要更新dis[i]

void djk(int x)
{
   dis[x] = 1e9+10;
   priority_queue<node> q;
   int y = 1e9+10;
   q.push({y,x});
   while(q.size())
   {
       auto k = q.top();
       q.pop();
       int w = k.x,v = k.y;
       if(vis[v])
       continue;
       vis[v] = 1;
       for(auto [ww,ne]:p[v])
       {
           if(dis[ne]<min(ww,dis[v]))
           {
               dis[ne] = min(ww,dis[v]);
               q.push({dis[v],ne});
           }
       }
   }

}

建议好好理解这部分

以后存图可以多用vector,十分方便

#include<iostream> #include<queue> #include<algorithm> using namespace std; int n,m,s; vector<pair<int,int>> p[]; int vis[]; int dis[]; struct node { int x,y; friend bool operator<(const node a,const node b) { return a.x<b.x; } }; void djk(int x) { dis[x] = 1e9+10; priority_queue<node> q; int y = 1e9+10; q.push({y,x}); while(q.size()) { auto k = q.top(); q.pop(); int w = k.x,v = k.y; if(vis[v]) continue; vis[v] = 1; for(auto [ww,ne]:p[v]) { if(dis[ne]<min(ww,dis[v])) { dis[ne] = min(ww,dis[v]); q.push({dis[v],ne}); } } } } int main() { cin >> n >> m >>s; for(int i = 1;i <= m;i++) { int l,r,x; cin >> l >> r>>x; p[l].push_back({r,x}); } djk(s); dis[s] = 0; for(int i = 1;i <= n; i++) { if(!dis[0]) { cout<<-1<<" "; } else { cout<<dis[i]<<" "; } } }

点分治分点(BFS)

相关推荐