题解：P10669 BZOJ3118 Orz the MST

· · 题解

太菜了不会线性规划

先分析出一个性质，树边只减小，非树边只增加。然后直接套保序回归。

复杂度不太会分析，但是只跑了 50 ms。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1010,M=6e5+500,inf=1e9;
int S,T,n,m,q[N],q1[N],q2[N],ans[N];
int vis[N];
vector<int>G[N];
bool fg[N];
struct edge{
    int a,b,ff,w,u,v;
}len[N];
namespace flow{
    int h[N],ne[M],e[M],idx=1,w[M],cnt[N],dis[N],cur[N],tot;
    inline void add(int u,int v,ll x1,ll x2){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w[idx]=x1;
        ne[++idx]=h[v],h[v]=idx,e[idx]=u,w[idx]=x2;
    }
    inline void init(int t1){
        tot=t1+2,S=t1+1,T=t1+2;
    }
    inline int dfs(int u,int sum){
        if(u==T) return sum;
        int ss=0;
        for(int &i=cur[u];i;i=ne[i]){
            int v=e[i];
            if(w[i]<=0||dis[u]!=dis[v]+1) continue;
            int tmp=dfs(v,min(w[i],sum-ss));
            ss+=tmp,w[i]-=tmp,w[i^1]+=tmp;
            if(sum==ss||dis[S]>=tot) return ss;
        }
        if(!--cnt[dis[u]]) dis[S]=tot;
        ++cnt[++dis[u]];
        cur[u]=h[u];
        return ss;
    }
    inline void ddd(int u){
        fg[u]=1;
        for(int i=h[u];i;i=ne[i]){
            int v=e[i];
            if(w[i]&&!fg[v]) ddd(v);
        }
    }
    inline void work(){
        for(int i=1;i<=tot;++i) cur[i]=h[i];
        ll res=0;
        while(dis[S]<tot) res+=dfs(S,inf);
        ddd(S);
        idx=1;
        memset(h,0,sizeof(int)*(tot+1));
        memset(cnt,0,sizeof(int)*(tot+1));
        memset(dis,0,sizeof(int)*(tot+1));
    }
}
using flow::init;
using flow::work;
ll d[N];
inline void solve(int l,int r,int L,int R){
    if(l>r) return ;
    if(L==R){
        for(int i=l;i<=r;++i) ans[q[i]]=L;
        return ;
    }
    flow::init(r-l+1);
    int mid=L+R>>1;
    for(int i=l;i<=r;++i) vis[q[i]]=i-l+1;
    for(int i=l;i<=r;++i){
        d[i]=(len[q[i]].ff?len[q[i]].b:len[q[i]].a)*(abs(mid-len[q[i]].w)-abs(mid+1-len[q[i]].w));
        if(d[i]>0) flow::add(S,i-l+1,d[i],0);
        else flow::add(i-l+1,T,-d[i],0);
        for(int v:G[q[i]]){
            if(vis[v]) flow::add(i-l+1,vis[v],inf,0);
        }
    }
    for(int i=l;i<=r;++i) vis[q[i]]=0;
    flow::work();
    int hh1=0,hh2=0;
    for(int i=l;i<=r;++i){
        if(!fg[i-l+1]) q1[++hh1]=q[i];
        else q2[++hh2]=q[i],fg[i-l+1]=0;
    }
    fg[r-l+2]=fg[r-l+3]=0;
    for(int i=1;i<=hh1;++i) q[l+i-1]=q1[i];
    for(int i=1;i<=hh2;++i) q[l+hh1+i-1]=q2[i];
    solve(l,l+hh1-1,L,mid),solve(l+hh1,r,mid+1,R);
}
int h[N],ne[N<<1],e[N<<1],w[N<<1],idx=1,fa[N],dep[N];
inline void add(int u,int v,int x){
    ne[++idx]=h[u],h[u]=idx,e[idx]=v,w[idx]=x;
    ne[++idx]=h[v],h[v]=idx,e[idx]=u,w[idx]=x;
}
inline void dfs(int u){
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];
        if(v!=e[fa[u]]) fa[v]=i^1,dep[v]=dep[u]+1,dfs(v);
    }
}
inline void link(int u,int v,int i){
    while(u!=v){
        if(dep[v]>dep[u]) swap(u,v);
        G[w[fa[u]]].push_back(i);
        u=e[fa[u]];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int l=1010,r=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d%d%d",&len[i].u,&len[i].v,&len[i].w,&len[i].ff,&len[i].a,&len[i].b);
        if(len[i].ff) add(len[i].u,len[i].v,i);
        l=min(l,len[i].w);
        r=max(r,len[i].w);
        q[i]=i;
    }
    dfs(1);
    for(int i=1;i<=m;++i){
        if(!len[i].ff) link(len[i].u,len[i].v,i);
    }
    solve(1,m,l-m,r+m);
    ll res=0;
    for(int i=1;i<=m;++i){
        if(ans[i]<len[i].w) res+=1ll*len[i].b*(len[i].w-ans[i]);
        else res+=1ll*len[i].a*(ans[i]-len[i].w);
    }
    printf("%lld",res);
    return 0;
}