Preorder

我的思路：
对于每次询问把那条边删掉跑一遍最短路和原最短路比较一下就行了，O(qm log n)只有5分。。。2333
正确的思路
考虑S到T的最短路图，即所有dist(S,u)+dist(v,T)+w的边组成的有向图。
这一定是一个有向无环图（DAG）。
那么一个S到T的最短路是且仅是一条最短路图上S到T的路径。
如果一条边不在最短路图上，则这条边删掉一定不会对最短路产生任何影响。
如果一条边在最短路图上，则考虑这条边删掉之后这个最短路图还连不连通就行了。
于是变成了DAG上删掉一条边判S到T的连通性问题。有两种做法：

1. 如果一条边被删了就不连通，那么这条边一定是原图变成无向图之后的割边，跑一遍Tarjan就行了。
2. 假设给每条边新建一个点e’，那么就加两条边(u,e’),(e’,v)。那么一条边删了就不连通当且仅当 是原图的一个支配点。

一个支配点。从S开始跑一遍DAG上的支配树就行了，然后所有支配点就是T在支配树上和S路径上的点。至于DAG上支配树怎么建，就直接按拓扑序考虑，然后每次考虑点u的时候，考虑所有(v,u)<=E的边，把所有v求个LCA就行了

#include
#define ll long long
using namespace std;
multiset <int> Buy,Sell;
inline int read()
{char c=getchar();int x=0,flag=1;while(!isdigit(c)){if(c=='-') flag=-1;c=getchar();}while(isdigit(c)) x=x*10+c-'0',c=getchar();return x*flag;
}
int main()
{int n=read(),L=read(),b=read(),s=read();ll ans=0;Buy.insert(b);Sell.insert(s);for(int i=2;i<=n;i++){b=read(),s=read();if(b<*Sell.rbegin()) {ans+=*Sell.rbegin()-b;Buy.insert(*Sell.rbegin());Sell.erase(--Sell.end());Sell.insert(b);}else Buy.insert(b);if(s>*Buy.begin()){ans+=s-*Buy.begin();Sell.insert(*Buy.begin());Buy.erase(Buy.begin());Buy.insert(s);}else Sell.insert(s);while(Sell.size()>L) Sell.erase(Sell.begin());while(Buy.size()>L) Buy.erase(--Buy.end());}cout<<ans;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！