题解：P14122 [SCCPC 2021] Direction Setting

· · 题解

题目大意

挺简单的一道费用流题目，给定 n 个点以及 m 条边以及一个长度为 n 的数列 a，让你决定 m 条边的方向使得

ans = \sum\limits_{i=1}^n \max(0, d_i - a_i)

有最小值（d_i 表示有多少条边连向 i 号节点，即入度）。

解题思路

贪心的思路来想，我们要求得 ans 的最小值，那么每一个点的入度都要尽量小于当前的 a_i，超出了会有额外的花费，由于 n 和 m 比较小，所以可以考虑费用流。

由于先前的想法，我们可以将这一个点 i 和最终的汇点 t 连接两条边，一条容量为 a_i，权值为 0，表示只要入度在 a_i 以内那么就不需要花费，另外一条通量为正无穷但是花费为 1 表示超出了就要支付的额外的开销，按照费用流的跑法，必定是先选择最优的第一条边先走，再选择次优的第二条边走。

而对于源点 s，以及边 (u_j,v_j) 我们可以其看作是一个点 j，建立 s 到 j 的边以及 j 分别到 u_j 和 v_j 的边，容量都为 1，边权都为 0，表示可以从源点选择 u_i 和 v_i 的两个点中的一个跑最大流，由于容量都为 1，所以只能选择一个进行增广，这必然是一个二选一的局面，那么这道题的建模部分就做好了。

但是我们不难发现，这道题竟然还有第二问，但是这会比刚刚的建模要来得简单，按照上面的说法，若有一条边的其中一个点被增广了，那么 j 连向 u_j 和 v_j 的容量必定有一个是空的，表示了一条增广路径的花费，那么我们可以存储下以上两条边的下标，如果在跑完费用流后 j 连向 u_i 的边的容量为零，那么就说明这条边的连向是 v_i 连向 u_i，因为有一个入度的贡献贡献给了 u_i，只需要依此进行输出就好了。

代码如下

#include<bits/stdc++.h>
using namespace std;
int T,n,m,ans,ansc,s,t;
int jl[100005],cur[100005],pd[100005],dl[100005],cc[4000][2],ii;
struct sbb {
    int a,b,rl,bq;
};
vector<sbb>bian;
vector<int>qu[100005];
void add(int a,int b,int c,int d) {
    bian.push_back({a,b,c,d});
    bian.push_back({b,a,0,-d});
    int sz=bian.size();
    if(c==1&&d==0&&a!=s&&a!=t&&b!=s&&b!=t)cc[ii][0]=sz-2,cc[ii][1]=sz-1;
    qu[a].push_back(sz-2);
    qu[b].push_back(sz-1);
    return ;
}
int spfa() {
    for(int i=s; i<=t; i++)jl[i]=1e9,pd[i]=cur[i]=0;
    dl[0]=1,dl[1]=s,jl[s]=0;
    int f=0;
    while(f<dl[0]) {
        int wz=dl[++f];
        pd[wz]=0;
        for(auto I:qu[wz]) {
            int nwz=bian[I].b;
            if(jl[nwz]<=jl[wz]+bian[I].bq||bian[I].rl<=0)continue;
            jl[nwz]=jl[wz]+bian[I].bq;
            if(pd[nwz]==0)pd[nwz]=1,dl[++dl[0]]=nwz;
        }
    }
    return (jl[t]!=1e9);
}
int dfs(int wz,int mq) {
    if(wz==t)return mq;
    pd[wz]=1;
    int nans=0;
    for(int &I=cur[wz]; I<qu[wz].size(); I++) {
        int i=qu[wz][I];
        int nwz=bian[i].b,z;
        if(jl[nwz]!=jl[wz]+bian[i].bq||pd[nwz]==1||bian[i].rl<=0)continue;
        z=dfs(nwz,min(mq,bian[i].rl));
        ansc+=z*bian[i].bq,nans+=z,mq-=z,bian[i].rl-=z,bian[(i^1)].rl+=z;
        if(mq<=0)break;
    }
    pd[wz]=0;
    return nans;
}
int dn() {
    ans=0,ansc=0;
    while(spfa()==1)ans+=dfs(s,1e9);
    return ans;
}
int a[100005],x[4000],y[4000];
void chuli() {
    bian.clear();//多测记得清空
    for(int i=0; i<=3050; i++)qu[i].clear();
    cin>>n>>m;
    s=0,t=n+m+10;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int j=1; j<=m; j++) {
        ii=j;
        cin>>x[j]>>y[j];
        add(s,j,1,0);
        add(j,x[j]+m,1,0),add(j,y[j]+m,1,0);
    }
    for(int i=1; i<=n; i++)add(i+m,t,a[i],0),add(i+m,t,1e9,1);
    dn();
    cout<<ansc<<'\n';
    for(int i=1; i<=m; i++)cout<<(bian[cc[i][0]].rl!=0);
    cout<<'\n';
    return ;
}
int main() {
    cin>>T;
    while(T--)chuli();
    return 0;
}

小提示

  1. 本题有多测，所以记得要清空；
  2. 本题有 Special Judge，样例中的第一个的第二小问输出全是 1 是正确的（虽然好像没什么用）。