2023NOIP A层联测16 T3 货物运输
题目描述说这是一个仙人掌图，通常将问题转换为环和树的问题在使用圆方树来解决。
树解法
令 \(a_i=s_i-\frac{\sum s_i}{n}\) ，最终令 \(a_i=0\)。
通过树形 dp，从叶子节点向上转移，叶子节点要么向父亲拿资源，要么向父亲传资源，所以转移为：
环解法
令 \(a_i=s_i-\frac{\sum s_i}{n}\) ，最终令 \(a_i=0\)。
不妨设编号顺序为：\(1,2,3,\cdots,n\)。
\(x_i\) 表示点 \(i\) 向 \(i-1\) 运输了\(x_i\) 个单位的资源，若 \(x_i<0\) 那么是 \(i-1\) 向 \(i\) 运输，若 \(i=1\) 那么 \(1\) 向 \(n\) 运输。
有方程组：
移项化简后，我们发现有 \(x_i=x_1-X_i\)，若 \(i=1\)，则 \(X_1=0\)（化简到这里实际上只需要前 \(n-1\) 条方程），其中 \(X_i\) 为常数。
那么答案为 \(\sum w_i|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\) 没有限制的情况，可以看作有 \(w_i\) 个 \(X_i\)，取 \(\sum w_i\) 个数的中位数。复杂度为排序的 \(O(n \log n)\)。
仙人掌
将一个环看成树上的一个点，环与环之间相邻的点看成边，依旧从叶子节点开始做。节点是环，使用环的解决方法，如果环缺少或多出值，先赊账在与父亲相连的点上（因为自己的儿子已经转移完了，多出或者少于都只可以传递或来自父亲），对于非环的边采用类似于树形 \(dp\) 的解决方法。
实现
可以先建出圆方树，一个方点对应一个环或者一条边，使用方点转移即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5,maxm=1e6+5;
struct node
{
int to,nxt;
}edge[maxn*4],tred[maxm];
int n,m,trtot,tot,tp,cok,tx,pj,ans;
int head[maxn],trhead[maxm],s[maxn],dfn[maxn],low[maxn],stk[maxn],sz[maxn],f[maxn];
vector<int>vec[maxm];
map<pair<int,int>,int>mp;
void add(int &tot,int head[],node edge[],int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void tarjin(int u)//建圆方树
{
dfn[u]=low[u]=++cok;
stk[++tp]=u;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!dfn[v])
{
tarjin(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
add(trtot,trhead,tred,++tx,u);
add(trtot,trhead,tred,u,tx);
vec[tx].push_back(u);
int x=0;
do
{
x=stk[tp--];
add(trtot,trhead,tred,tx,x);
add(trtot,trhead,tred,x,tx);
vec[tx].push_back(x);
}while(x!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs2(int u)//遍历圆方树求答案
{
int sum=0;
for(int i=trhead[u];i;i=tred[i].nxt)
{
int v=tred[i].to;
if(v==f[u]) continue;
dfs2(v);
if(u>n) sum+=s[v];
}
if(u<=n) return ;
if(vec[u].size()==2)//非环边直接转移
{
int son;
if(vec[u][0]==f[u]) son=vec[u][1];
else son=vec[u][0];
s[f[u]]+=s[son];
ans+=abs(s[son])*mp[make_pair(f[u],son)];
return ;
}
priority_queue< pair<int,int>,vector< pair<int,int> >, greater< pair<int,int> > >que;//环边
while(!que.empty()) que.pop();
int cnt=vec[u].size();
sum+=s[f[u]];
int tmp=s[f[u]];
s[f[u]]=s[f[u]]-sum;
que.push(make_pair(0,mp[ make_pair(vec[u][0],vec[u][cnt-1]) ]));
int ct=0,sg=mp[ make_pair(vec[u][0],vec[u][cnt-1]) ];
for(int i=1;i<cnt;i++)
{
int w=mp[ make_pair(vec[u][i],vec[u][i-1]) ];
ct+=s[ vec[u][i-1] ];
que.push(make_pair(ct,w)),sg+=w;
}
ct=0;
int x=0;
while(!que.empty())//中位数
{
ct+=que.top().second;
if(ct>sg/2) {x=que.top().first;break;}
que.pop();
}
ct=0;
ans+=abs(ct-x)*mp[make_pair(vec[u][0],vec[u][cnt-1])];
for(int i=1;i<cnt;i++)
{
int w=mp[ make_pair(vec[u][i],vec[u][i-1]) ];
ct+=s[ vec[u][i-1] ];
ans+=w*abs(x-ct);
}
s[f[u]]=sum;
}
void dfs1(int u,int fa)
{
f[u]=fa;
for(int i=trhead[u];i;i=tred[i].nxt)
{
int v=tred[i].to;
if(v==fa) continue;
dfs1(v,u);
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&s[i]),pj+=s[i];
pj/=n;
for(int i=1;i<=n;i++) s[i]=s[i]-pj;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(tot,head,edge,x,y);
add(tot,head,edge,y,x);
mp[make_pair(x,y)]=z;
mp[make_pair(y,x)]=z;
}
tx=n;
tarjin(1);
dfs1(n,0);//答案是在计算过程中统计的，所以出发点设为圆点更方便统计
dfs2(n);
printf("%lld",ans);
}