题解：CF2046D For the Emperor!

Milmon · 2024-12-05 19:50:37 · 题解

Statement

有一张 n 个点 m 条边的有向图，第 i 个点上有 a_i 个人。

你可以选择一些结点发放一份计划，接下来每个人可以沿着边自由移动，如果一个人从一个收到过计划的点移动到一个没有收到计划的点，那么可以令其收到计划。

你需要让所有的点都收到计划，求最少需要在多少个结点发放计划，或者报告无解。

数据范围：数据组数 T \leq 100，2 \leq n \leq 200，1 \leq m \leq 800，0 \leq a_i \leq n。

Solution

考虑建立费用流模型，核心思想是让最大流量总是 \sum a_i，而经过一个点的费用是 -B（B 是一个极大的数），在一个点发放计划的费用是 1，这样求出最小费用之后，可以根据其除以 B 的整数部分计算其最多能让多少个点收到计划，根据余数计算出该前提下最小发放计划的数量。

记源点为 S，汇点为 T。考虑按照下述方案连边：

为了限制从一个点 u 出发的人的数量为 a_u，先建立一个约束点 F_u，连一条流量为 a_u 的边 S \to F_u。
考虑为一个点 u 建立一个入点 P_u 和一个出点 Q_u，流过 P_u \to Q_u 这条边就认为一个人走过的路径经过了点 u。要让第一次经过产生 -B 的费用，之后不产生费用，只需要连两条流量分别为 1 和 +\infty、费用分别为 -B 和 0 的边即可。
为了让一开始发放计划的点产生 1 的费用，而当点被经过之后从该点出发不产生 1 的费用，只需连边 F_u \to P_u，流量和费用均为 1，再连边 F_u \to Q_u，流量为 +\infty，费用为 0。如果 F_u \to Q_u 被经过，那么 P_u \to Q_u 的费用为 -B 的边一定被经过，此时点 u 已经被发放计划，所以不产生贡献。
对于原图的有向边 u \to v，需要连边 Q_u \to P_v。
最后当人结束移动时流向汇点，即连边 Q_u \to T。

如果原图存在环，那么需要先进行强联通分量缩点，a 的值为 SCC 内所有点的 a 的值的和。

按照上述方案连边，总点数是 \Theta(n) 的，总边数是 \Theta(n + m) 的，使用最小费用最大流解决可以接受。

Solution (English)

Consider constructing a cost-flow model. The core idea is to ensure that the maximum flow is always \sum a_i, and the cost of passing through a point is -B (where B is a very large number). The cost of issuing a plan at a point is 1. After calculating the minimum cost, its integer part divided by B represents the maximum number of points that can receive the plan, while the remainder determines the minimum number of plans issued under this condition.

Let the source be S and the sink be T. Edges are constructed as follows:

To limit the number of people starting from a point u to a_u, introduce a constraint point F_u and connect an edge with capacity a_u from S \to F_u.
For a point u, create an entry node P_u and an exit node Q_u. If a path passes through the edge P_u \to Q_u, it means that someone has traversed point u. To ensure that the first traversal incurs a cost of -B while subsequent traversals incur no cost, simply add two edges with capacities 1 and +\infty, and costs -B and 0, respectively.
To ensure that issuing a plan at a point initially incurs a cost of 1, and subsequent departures from the point incur no cost, connect edges F_u \to P_u with both capacity and cost of 1, and F_u \to Q_u with capacity +\infty and cost 0. If the edge F_u \to Q_u is used, then the edge P_u \to Q_u with cost -B must have been traversed, indicating that point u has already been issued a plan and thus contributes no additional cost.
For a directed edge u \to v in the original graph, connect an edge Q_u \to P_v.
Finally, to allow people to end their movement at the sink, connect edges Q_u \to T.

If the original graph contains cycles, first perform a strongly connected components (SCC) contraction. The value of a for each SCC is the sum of the a values of all points within the SCC.

Following the above scheme for edge construction, the total number of nodes is \Theta(n), and the total number of edges is \Theta(n + m). Solving this using minimum-cost maximum-flow is accepted.

Code

#include<bits/stdc++.h>
using namespace std;
const int inf=1e5;

struct MinCostFlow{
    static const int N=602,M=2000;
    int n,cntEdge,head[N+1];
    struct Edge{
        int to,nxt,lim,cost;
    }edge[(M+1)*2];
    inline void addEdge(int u,int v,int lim,int cost){
        edge[++cntEdge]={v,head[u],lim,cost},head[u]=cntEdge;
        edge[++cntEdge]={u,head[v],0,-cost},head[v]=cntEdge;
    }
    inline void init(int _n){
        n=_n,cntEdge=1;
        memset(head,0,sizeof(int)*(n+1));
    }
    int dis[N+1],minn[N+1],pre[N+1],preEdge[N+1];
    bool inQueue[N+1];
    inline bool SPFA(int S,int T){
        memset(dis,0x7f,sizeof(int)*(n+1));
        memset(minn,0x7f,sizeof(int)*(n+1));
        memset(inQueue,false,sizeof(bool)*(n+1));
        queue<int> Q;
        Q.push(S),dis[S]=0,inQueue[S]=true,pre[T]=-1;
        while(!Q.empty()){
            int u=Q.front(); Q.pop();
            inQueue[u]=false;
            for(int i=head[u];i;i=edge[i].nxt){
                int v=edge[i].to;
                if(edge[i].lim&&dis[u]+edge[i].cost<dis[v]){
                    dis[v]=dis[u]+edge[i].cost;
                    pre[v]=u,preEdge[v]=i,minn[v]=min(minn[u],edge[i].lim);
                    if(!inQueue[v])Q.push(v),inQueue[v]=true;
                }
            }
        }
        return pre[T]!=-1;
    }
    inline pair<int,int> flow(int S,int T){
        int maxflow=0,mincost=0;
        while(SPFA(S,T)){
            maxflow+=minn[T],mincost+=minn[T]*dis[T];
            int u=T;
            while(u!=S){
                edge[preEdge[u]].lim-=minn[T];
                edge[preEdge[u]^1].lim+=minn[T];
                u=pre[u];
            }
        }
        return {maxflow,mincost};
    }
}G;

int n,m,a[201];
vector<int> E[201];

int dfn[201],low[201],cntdfn;
int cntscc,scc[201],siz[201];
bool vis[201];
stack<int> sta;
void tarjan(int u){
    dfn[u]=low[u]=++cntdfn,vis[u]=true,sta.push(u);
    for(int v :E[u]){
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc[u]=++cntscc,siz[cntscc]=0;
        int v;
        do v=sta.top(),sta.pop(),siz[cntscc]+=a[v],scc[v]=cntscc,vis[v]=false;
        while(v!=u);
    }
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)E[i].clear(),dfn[i]=low[i]=vis[i]=0;
        cntdfn=cntscc=0;
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            E[u].push_back(v);
        }
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
        G.init(cntscc*3+2);
        auto id=[&](int t,int u){
            return t*cntscc+u;
        };
        int S=id(3,1),T=id(3,2);
        for(int i=1;i<=cntscc;i++){
            if(siz[i]){
                G.addEdge(S,id(0,i),siz[i],0);
                G.addEdge(id(0,i),id(1,i),1,1);
                G.addEdge(id(0,i),id(2,i),inf,0);
            }
            G.addEdge(id(1,i),id(2,i),1,-inf);
            G.addEdge(id(1,i),id(2,i),inf,0);
            G.addEdge(id(2,i),T,inf,0);
        }
        for(int u=1;u<=n;u++)
            for(int v :E[u])if(scc[u]!=scc[v])
                G.addEdge(id(2,scc[u]),id(1,scc[v]),inf,0);
        int cost=-G.flow(S,T).second;
        int used=(inf-cost%inf)%inf,covered=(cost+used)/inf;
        printf("%d\n",covered==cntscc?used:-1);
    }
    return 0;
}