2023NOIP A层联测16 货物运输

本文主要是介绍2023NOIP A层联测16 货物运输，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有一个有 $n$ 个点 $m$ 条边的无向连通图，每条边的长度为 $w_i$ ，并且任意一条边最多在一个简单环内。每个点都有 $s_i$ 个单位的资源，你想要均分这些资源，即让每座城市的资源数等于 $\dfrac{\sum s_i}{n}$ （数据保证 $\dfrac{\sum s_i}{n}$ 是整数）。

已知将每个单位的资源运输到相邻城市需要花费道路长度 $w_i$ 的代价，求使得资源均分的最小代价。

$1\leq n\leq 10^5,n-1\leq m\leq 2n-2,0\leq w_i,s_i\leq 10^4$ 。

题解

首先，我们可以求出这个图的所有点双连通分量。然后，建一个新的图，在图上将每个点双连通分量建一个虚拟点，这个虚拟点和原图中点双连通分量中的点连边。

举个例子，我们来看下面这个图。

在这里插入图片描述

其中， ${1,2,3\}$ 是一个点双连通分量， ${3,4\}$ 是一个点双连通分量，那么我们将这两个点双连通分量虚拟成点，按上述方法连边，得到的图为

在这里插入图片描述

我们可以发现，这个图是一棵树。因为如果不是一棵树的话，那图上必定有一个环，那这个环又可以构成一个新的点双连通分量，矛盾。所以这个图一定是一棵树。

因为任意一条边最多在一个简单环内，所以这些点双连通分量其实都是一个环（也有可能是两个相连的点，这种情况特殊处理一下即可）。那么，我们对树的部分和每个点双连通分量的部分分别处理即可。

我们发现，这个新图的树边在原图对应的其实都是自己连向自己的，所以边权为 $0$ 。所以在树上只需要上传下面多出的资源（或者上传下面需要的资源），不需要统计对答案的贡献。那怎么上传呢？设点 $u$ 的子树内的有 $sum_u$ 个单位的资源，有 $siz_u$ 个点，则子树中只需要 $avg\times siz_u$ 个单位的资源（其中 $avg=\dfrac{\sum s_i}{n}$ ），其余 $sum_u-avg\times siz_u$ 个单位的资源一定会往上传（如果值为负的话就是要往下传这个数的绝对值）。

然后，我们考虑每个点双连通分量要怎么处理。对于新图中每个表示点双连通分量的虚拟点，在遍历完它的子树之后，除了这个虚拟点的父亲之外，这个虚拟点直接连向的所有点（也就是原图中其表示的点双连通分量中的点）的 $s_i$ 都已经确定了，而这个虚拟点的父亲有可能还会往其他地方传资源。

但是，我们是可以确定虚拟点的父亲往其他部分传完资源后剩下的资源的。我们假设这个环之外的部分都已经处理好了（就是环之外的点所含的资源都已经为 $a vg$ ），那么环上的点的资源之和就是环上的点数乘 $a vg$ 。不妨设环上每个点的编号为 $1,2,\dots,k$ ，一号点为新图中虚拟点的父亲所表示的点，设 $a_i=s_i-avg$ ，则最终要使环上所有点的 $a_i$ 变为 $0$ ，那么此时必定满足 $\sum\limits_{i=1}^ka_i=0$ 。而 $a_2,a_3,\dots,a_k$ 都是已经确定的，那么 $a_1=-\sum\limits_{i=2}^ka_i$ 。

那么，我们现在已经得出环上每个点的 $a_i$ ，其表示这个点当前的资源与 $a vg$ 的差，下面考虑怎么才能让所有 $a_i$ 都等于 $0$ 。

设 $x_i$ 表示 $i$ 向 $i - 1$ 运输的资源数量，当 $x_i<0$ 时表示从 $i - 1$ 向 $i$ 运输 $x_i|$ 个单位的资源。那么，可以列出方程组：

$\left\{\begin{matrix} a_1-x_1+x_2=0 \\ a_2-x_2+x_3=0 \\ \cdots \ \cdots \\ a_n-x_n+x_1=0 \end{matrix}\right.$

解得

$\begin{cases} x_2=x_1-a_1 \\ x_3=x_2-a_2=x_1-a_1-a_2 \\ \cdots \ \cdots \\ x_n=x_1-a_1-a_2-\cdots-a_{n-1} \end{cases}$

因此，每个 $x_i$ 都可以用 $x_1$ 表示： $x_i=x_1+X_i$ ，那么最后的答案为 $\sum w_i|x_1-X_i|$ 。

那么，问题转化为求 $x_1$ 的值，使得 $\sum w_i|x_1-X_i|$ 最小。当 $w_i$ 都为 $1$ 时， $x_1$ 直接取 $X_i$ 的中位数；当 $w_i$ 不都为 $1$ 时，可以看作有 $w_i$ 个 $X_i$ ， $x_1$ 取 $\sum w_i$ 个数的中位数。然后，求出 $\sum w_i|x_1-X_i|$ 的值并用其更新答案即可。

注意要特判点双连通分量为两个相连的点的情况。

对于端点和边权分别为 $u_i,v_i,w_i$ ，我们可以用 $ma p$ 来存边权，即 $mp[u_i][v_i]=w_i$ ，这样可以很方便地调用边权。

时间复杂度为 $O((n+m)\log n)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000,M=200000;
int n,m,avg=0,tot=0,d[2*M+5],l[2*M+5],r[N+5],z[N+5],s[N+5];
int ct=0,vt=0,tp=0,dfn[N+5],low[N+5],st[N+5],sum[2*N+5],siz[2*N+5];
long long ans=0;
struct node{int x,sum;
};
struct vp{int x,w;
};
map<int,int>mp[N+5];
vector<int>vd[2*N+5];
vector<node>p;
vector<vp>c;
bool cmp(vp ax,vp bx){return ax.x<bx.x;
}
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs1(int u,int fa){st[++tp]=u;low[u]=dfn[u]=++ct;for(int i=r[u];i;i=l[i]){int v=d[i];if(v==fa) continue;if(!dfn[v]){dfs1(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<=low[v]){int th;++vt;do{th=st[tp];--tp;vd[vt].push_back(th);vd[th].push_back(vt);}while(th!=v);vd[vt].push_back(u);vd[u].push_back(vt);}}else low[u]=min(low[u],dfn[v]);}
}
void solve(){if(p.size()==2){ans+=1ll*mp[p[0].x][p[1].x]*abs(p[0].sum);return;}c.clear();int vx=0;c.push_back((vp){vx,mp[p.back().x][p.front().x]});int sum=mp[p.back().x][p.front().x];for(int i=1;i<p.size();i++){vx+=p[i-1].sum;c.push_back((vp){vx,mp[p[i-1].x][p[i].x]});sum+=mp[p[i-1].x][p[i].x];}sort(c.begin(),c.end(),cmp);int now=0,chx;for(int i=0;i<c.size();i++){now+=c[i].w;if(now>=(sum+1)/2){chx=c[i].x;break;}}for(int i=0;i<c.size();i++){ans+=1ll*abs(chx-c[i].x)*c[i].w;}
}
void dfs2(int u,int fa){if(u<=n){sum[u]=s[u];siz[u]=1;}for(int i=0;i<vd[u].size();i++){int v=vd[u][i];if(v==fa) continue;dfs2(v,u);sum[u]+=sum[v];siz[u]+=siz[v];}if(u>n){p.clear();int sf=0;for(int i=0;i<vd[u].size();i++){int v=vd[u][i];if(v==fa) continue;p.push_back((node){v,siz[v]*avg-sum[v]});sf-=siz[v]*avg-sum[v];}p.push_back((node){fa,sf});solve();}
}
int main()
{
//	freopen("transfer.in","r",stdin);
//	freopen("transfer.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&s[i]);avg+=s[i];}avg/=n;for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y);add(y,x);mp[x][y]=mp[y][x]=z;}vt=n;dfs1(1,0);dfs2(1,0);printf("%lld",ans);return 0;
}