题解：P9901 『PG2』弯曲半平面直线同向图最大流

· · 题解

本蒟蒻没看懂题解然后很无脑的过了此题，于是来写这篇题解。时间复杂度 O(n \log n)，但是瓶颈在排序。（虽然我并不信任 vector 的常数但是 sort 的常数还是非常可靠的，跑个 10^6 没有任何问题。）

首先这是一个求最大流的问题，因此把所有无关点去掉。其次由题易得根据定义可以看出来这是个 DAG，因此对于剩下的点无脑拓扑排序。接下来显然的我们可以把所有点按拓扑序放置在一条直线上。（没错，这一段处理比核心代码还长。）

这个图最外层是几段连在一起的弧，我们考虑处理每一段弧下面的最大流，因此我们可以考虑分治。处理完下面的最大流之后整段的最大流就是上面一条弧的流量的加上下面的最大流的最小值。由于每一条边都要过一遍，所以这里时间复杂度是 O(n)（n，m 同级）。

最后关于实现的问题，就是说怎么处理哪些弧在上面哪些弧在下面的问题，我采用的实现方法是每次分治时跳的尽量远然后标记一下这条边走过了。这就需要排序了。

代码：

//Always trust in sort,never believe vector.
#include<bits/stdc++.h>
//#define int long long 这里真的不需要long long就能过？
using namespace std;
const int N=2000050;//m<=2n-3
int U[N],V[N],W[N],vis[N],rd[N],to[N],now[N],pr[N],Pr[N],rp[N],Rp[N]; 
vector<int>ord,vec;
void dfsG(int x){if(vis[x])return;
vis[x]=N;for(int i=Pr[x];i;i=pr[i])dfsG(V[i]);}
void dfsR(int x){if(vis[x]%N)return;
vis[x]++;for(int i=Rp[x];i;i=rp[i])dfsR(U[i]);}
bool cmp(int a,int b){return V[a]>V[b];}
inline int read(){
    register int x=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int solve(int L,int R){//想不到吧，核心代码这么短
    if(L==R)return 0;
    int L2=L,mn=0x3f3f3f3f;
    while(L2!=R){
        if(!V[now[L2]])return 0;
        int tmp=now[L2];
        now[L2]=pr[now[L2]];
        int L3=V[tmp],w=W[tmp];
        mn=min(mn,w+solve(L2,L3));
        L2=L3;
    }
    return mn;
}
void Sort(int x){
    if(!x)return;
    vec.clear();
    for(int i=now[x];i;i=pr[i]){
        vec.push_back(i);
    }
    if(vec.empty())return;
    sort(vec.begin(),vec.end(),cmp);
    now[x]=vec[0];
    for(int i=0;i<vec.size()-1;i++){
        pr[vec[i]]=vec[i+1];
    }
    pr[vec[vec.size()-1]]=0;
}
signed main(){
    int n,m,s,t,flag=0;
    n=read(),m=read(),s=read(),t=read();//一定要用快读
    for(int i=1;i<=m;i++)U[i]=read(),V[i]=read(),W[i]=read()
    ,pr[i]=Pr[U[i]],Pr[U[i]]=i,rp[i]=Rp[V[i]],Rp[V[i]]=i,rd[V[i]]++;
    dfsG(s),dfsR(t);queue<int>Q;for(int i=1;i<=m;i++)Q.push(!rd[i]*i);
    while(Q.size()){
        int h=Q.front();Q.pop();if(vis[h]>N)ord.push_back(h);
        for(int i=Pr[h];i;i=pr[i])if(!--rd[V[i]])Q.push(V[i]);
    }//拓扑
    for(int i=0;i<ord.size();i++)to[ord[i]]=i+1;
    for(int i=1;i<=m;i++)U[i]=to[U[i]],V[i]=to[V[i]];
    for(int i=1;i<=n;i++)now[to[i]]=Pr[i];
    for(int i=1;i<=ord.size();i++)Sort(i);
    if(V[now[1]]==ord.size())flag=W[now[1]],now[1]=pr[now[1]];
    cout<<flag+solve(1,ord.size());
    return 0;
}
//码风清奇，请见谅