网站页面制作公司,wordpress插件 下载,软件工程技术学什么,开发平台教程正题
题目链接:https://www.luogu.com.cn/problem/P2483 题目大意
给出一个nnn个点mmm条边的一张带权有向图#xff0c;求一个最大的kkk使得1∼n1\sim n1∼n的前kkk短路径长度和不超过EEE。 2≤n≤5000,1≤m≤2105,1≤E≤1072\leq n\leq 5000,1\leq m\leq 2\times 10^5,1\le…正题
题目链接:https://www.luogu.com.cn/problem/P2483 题目大意
给出一个nnn个点mmm条边的一张带权有向图求一个最大的kkk使得1∼n1\sim n1∼n的前kkk短路径长度和不超过EEE。
2≤n≤5000,1≤m≤2×105,1≤E≤1072\leq n\leq 5000,1\leq m\leq 2\times 10^5,1\leq E\leq 10^72≤n≤5000,1≤m≤2×105,1≤E≤107 解题思路
我们先把从nnn出发的一棵反向最短路树跑出来注意这里的最短路树是真的一棵树我们从DAGDAGDAG中随便提一些边出来构成一棵树以nnn为根。
然后考虑我们将其他的路径中不在树上的路径拿出来那么这些边肯定满足前一条边的终点ttt肯定在后一条边起点sss的子树中。
如果我们能确定这样一个有序的边集就相当于确定了这样一条唯一的路径。
然后考虑一条边(x,y,w)(x,y,w)(x,y,w)的边权视为disy−disxwdis_y-dis_xwdisy−disxw这样最终的路径长度就是dis1dis_1dis1加上这些边的权值和。
然后考虑怎么去扩展我们的方案假设我们现在的边集EEE的倒数第一个和最后一个分别是(x′,y′,w′),(x,y,w)(x,y,w),(x,y,w)(x′,y′,w′),(x,y,w)
那么我们有两种扩展方式
在最后加一条边这条边的起点一点得是yyy或yyy的祖先。替换最后一条边这条边必须是起点是y′yy′或其祖先中恰好比当前这条边权大的边。
因为有重复边权我们还是给每条边一个具体的顺序。
然后用堆维护最后两条边的状态就好了主席树维护每个点其祖先的所有出边的一棵权值线段树。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#includemap
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N2e510,MN5;
const double eps1e-8;
struct edge{int x,y;bool ban;double w;
}e[N];
struct node{int to,next,w;
}a[N];
int n,m,tot,ans,ls[N],ban[N],fa[N],rt[N];
double f[N],k;bool v[N];mapint,int u[N];
vectorint T[N],ot[N];
priority_queuepairdouble,int _q;
priority_queuepairdouble,pairint,int q;
struct SegTree{int cnt,w[M],ls[M],rs[M];int Change(int x,int L,int R,int pos){int pcnt;w[p]w[x]1;if(LR)return p;int mid(LR)1;if(posmid)ls[p]Change(ls[x],L,mid,pos),rs[p]rs[x];else rs[p]Change(rs[x],mid1,R,pos),ls[p]ls[x];return p;}int Ask(int x,int L,int R,int k){if(kR||!w[x])return 0;if(LR)return L;int mid(LR)1;if(kmid)return Ask(rs[x],mid1,R,k);int ansAsk(ls[x],L,mid,k);if(!ans)ansAsk(rs[x],mid1,R,k);return ans;}
}S;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dij(){for(int i1;in;i)f[i]1e100;_q.push(mp(0,n));while(!_q.empty()){int x_q.top().second;_q.pop();if(v[x])continue;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]e[a[i].w].wf[y]){f[y]f[x]e[a[i].w].w;ban[y]a[i].w;fa[y]x;_q.push(mp(-f[y],y));}}}return;
}
bool cmp(edge x,edge y)
{return x.wy.w;}
void dfs(int x){for(int i0;iot[x].size();i)rt[x]S.Change(rt[x],1,m,ot[x][i]);for(int i0;iT[x].size();i)rt[T[x][i]]rt[x],dfs(T[x][i]);return;
}
void solve(){int xS.Ask(rt[1],1,m,0);q.push(mp(-f[1]-e[x].w,mp(1,x)));while(!q.empty()){double w-q.top().first;int xq.top().second.first;int yq.top().second.second;q.pop();if(kepsw){ans,ans--;return;}k-w;ans;int pS.Ask(rt[e[y].y],1,m,1);if(p)q.push(mp(-w-e[p].w,mp(e[y].y,p)));pS.Ask(rt[x],1,m,y1);if(p)q.push(mp(-we[y].w-e[p].w,mp(x,p)));}
}
int main()
{
// freopen(P2483_3.in,r,stdin);scanf(%d%d%lf,n,m,k);for(int i1;im;i){scanf(%d%d%lf,e[i].x,e[i].y,e[i].w);addl(e[i].y,e[i].x,i);}dij();if(kf[1])return puts(0)0;k-f[1];ans;for(int i1;in;i)e[ban[i]].ban1;for(int i1;in;i)T[fa[i]].push_back(i);for(int i1;im;i)if(!e[i].bane[i].x!n)e[i].wf[e[i].y]e[i].w-f[e[i].x];else swap(e[i],e[m]),m--,i--;sort(e1,e1m,cmp);for(int i1;im;i)ot[e[i].x].push_back(i);dfs(n);solve();printf(%d\n,ans);return 0;
}
