题解：CF2046D For the Emperor!

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

CPP

#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;
}

题解：CF2046D For the Emperor!

文章操作

Statement

Solution

Solution (English)

Code

相关推荐

评论

题解：CF2046D For the Emperor!