自动搬运

查看原文

来自洛谷，原作者为

	mRXxy0o0 风轻抚过琴弦，也吹乱一时思绪

搬运于2025-08-24 23:00:06，当前版本为作者最后更新于2024-08-15 23:31:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

太菜了不会线性规划

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

复杂度不太会分析，但是只跑了 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;
}