CF1951I 题解

· · 题解

Problem Link

题目大意

给定 n 个点 m 条边的图，求出 k 个生成树，对于一条边 e，如果其在 x_e 个生成树中，那么花费是 a_ex^2_e+b_ex_e，最小化总花费。

数据范围：n,m\le 50，k\le 10^7。

思路分析

本题可能需要一些有关 Matroid Union 和 Matroid Partition 的知识，有兴趣的话可以移步本人博客：Link。

先考虑如何检验一个 \{x_e\} 数组是否合法（或可能合法）。

即需判定：对于给定边集 E，是否存在一种把 E 划分为 k 个森林的方式。

这是一个 Matroid Partition 问题，可以建立图拟阵 M=(E,\mathbf I)，其中 \mathbf I 是所有无环的 E 的子集构成的集合。

我们只要求出最小的 k 使得 E 能被拆成 k 个 \mathbf I 中元素的并。

根据 Nash-Williams 定理可得：\forall A\subseteq E, k_{\min}\times r(A)\ge |A|。

也就是对于每个边集 A，r(A) 就是 A 中每个连通块的端点数 -1 的和，根据糖水原理，A 的限制肯定不如其每个连通块单独的限制紧。

因此我们只要考虑那些联通的边集 A，设其端点集合为 V，那么 r(A)=|V|-1，注意这里只在 A 非空时成立。

因此判定题目中给出的 k 是否合法，相当于 0\ge \max_A |A|-k(|V|-1)。

那么我们只要判断对于每个 A，是否总是满足 \max_A |A|-k|V|\le -k，这是一个经典的最大权闭合子图模型，每个边建点，权值为 x_e，连向 u_e,v_e，每个端点权值为 -k，判断最大权闭合子图的权值是否 \le -k。

但此时如果取 A=\varnothing 是不合法的，因此我们要钦定取出的点集非空，我们枚举一个端点，强制选择即可。

此时我们跑 n 次网络流，那么 check 一组 \{x_e\} 的复杂度是 \mathcal O(n\times \mathrm{Flow}(n+m,n+m))。

然后考虑原题。

我们可以接着用拟阵贪心来解决：对每条边拆成 k 份，第 e 条边的第 i 个版本的权值为 a_ei^2+b_ei-a_e(i-1)^2-b_e(i-1)=2a_ei+b_e-a_e。

那么一条边选 x 次，一定相当于选这条边的第 1\sim x 个版本，总贡献恰好正确。

那么对新的边集 E 建拟阵 M=(E,\mathbf I)，其中 \mathbf I 是所有能被划分成 k 个森林的边集构成的集合，由于 \mathbf I 能看成 k 个图拟阵的并，因此 M 是拟阵。

那么我们要求的就是拟阵上权值最小的一组基。

根据拟阵上的贪心过程（类似 Kruskal）：我们把所有边按权值排序，从小到大能加入就加入。

那么我们可以二分优化这个过程，二分一个斜率 d，把每条边权值 \le d 的版本全部加入，即取 x_e=\left\lfloor\dfrac{d-b_e+a_e}{2a_e}\right\rfloor，然后 check 这组 x 是否合法。

找到最大的合法的 d，那么我们知道，加入所有斜率为 d+1 的边后会不合法，那么我们逐条加入斜率为 d+1 的边，如果某个 e 加入后不合法，那么说明 x_e 不能再增加了，取 x_e=\left\lfloor\dfrac{d-b_e+a_e}{2a_e}\right\rfloor 并且在之后的过程中不改变 x_e 即可。

这样的操作至多进行 m 轮，每轮删掉一条边。

时间复杂度 \mathcal O(m(m+\log V)\times n\times \mathrm{Flow}(n+m,n+m))。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace F {
const int MAXV=205,MAXE=2005;
const ll inf=1e18;
int hd[MAXV],dep[MAXV],cur[MAXV],ec,S,T;
struct Edge { int v,e; ll f; }  G[MAXE];
void add(int u,int v,ll f) { G[++ec]={v,hd[u],f},hd[u]=ec; }
void link(int u,int v,ll f) { add(v,u,0),add(u,v,f); }
void init() { ec=1,memset(hd,0,sizeof(hd)); }
bool bfs() {
    memset(dep,-1,sizeof(dep));
    memcpy(cur,hd,sizeof(cur));
    queue <int> Q; Q.push(S),dep[S]=0;
    while(Q.size()) {
        int u=Q.front(); Q.pop();
        for(int i=hd[u];i;i=G[i].e) if(G[i].f) {
            int v=G[i].v;
            if(dep[v]==-1) dep[v]=dep[u]+1,Q.push(v);
        }
    }
    return ~dep[T];
}
ll dfs(int u,ll f) {
    if(u==T) return f;
    ll r=f;
    for(int i=cur[u];i&&r;i=G[i].e) {
        int v=G[cur[u]=i].v;
        if(dep[v]==dep[u]+1&&G[i].f) {
            ll g=dfs(v,min(r,G[i].f));
            if(!g) dep[v]=-1;
            G[i].f-=g,G[i^1].f+=g,r-=g;
        }
    }
    return f-r;
}
ll dinic() {
    ll ans=0;
    while(bfs()) ans+=dfs(S,inf);
    return ans;
}
}
using F::link;
const int MAXN=55;
const ll inf=1e18;
ll a[MAXN],b[MAXN],x[MAXN],k;
int n,m,u[MAXN],v[MAXN];
bool del[MAXN],h[MAXN];
ll cnt(int i,ll d) { //cnt [slope<=d]
    return max(0ll,(d-b[i]+a[i])/(2*a[i]));
}
bool check(ll d) {
    for(int i=1;i<=m;++i) if(!del[i]&&cnt(i,d+h[i])>k) return false;
    for(int p=1;p<=n;++p) {
        int s=F::S=n+m+1,t=F::T=s+1;
        ll tot=-k; F::init();
        for(int i=1;i<=n;++i) if(i!=p) link(i+m,t,k);
        for(int i=1;i<=m;++i) {
            ll q=del[i]?x[i]:cnt(i,d+h[i]);
            tot+=q,link(s,i,q);
            link(i,u[i]+m,inf);
            link(i,v[i]+m,inf);
        }
        tot-=F::dinic();
        if(tot>-k) return false;
    }
    return true;
}
void solve() {
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=m;++i) scanf("%d%d%lld%lld",&u[i],&v[i],&a[i],&b[i]),x[i]=del[i]=0;
    for(int T=1;T<=m;++T) {
        for(int i=1;i<=m;++i) h[i]=0;
        ll l=0,r=inf,d=inf;
        while(l<=r) {
            ll mid=(l+r)>>1;
            if(check(mid)) d=mid,l=mid+1;
            else r=mid-1;
        }
        for(int i=1;i<=m;++i) if(!del[i]) {
            h[i]=1;
            if(cnt(i,d+1)>cnt(i,d)&&!check(d)) {
                x[i]=cnt(i,d),del[i]=true; break;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=m;++i) ans+=x[i]*x[i]*a[i]+x[i]*b[i];
    printf("%lld\n",ans);
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}