[NOI 2006] 最大获利

AuZeb · 2025-03-07 20:43:30 · 题解

思路

本题可转化为最大权闭合图问题。最大权闭合图是指在一个有向图中，对于图中的任意一个点，其所有出边指向的点都在该闭合图内，且该闭合图的权值之和最大。

1. 节点设置：

   • 设立一个源点 S 和一个汇点 T。

2. 边的构建：

   • 从源点 S 向每个用户节点连接一条边，边的容量为该用户的获利 c_i。
   • 从每个用户节点向其依赖的两个基地节点各连接一条容量为无穷大的边。无穷大的容量保证了在最小割计算时，这条边不会成为割边。
   • 从每个基地节点向汇点 T 连接一条边，边的容量为基地的成本 p_i。

最终输出总收益减去最小割（最大流）。

样例如下图：

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5003,M=50004,INF=0x3f3f3f3f;
struct Edge{int to,cap,flow,ne;}e[M*6+N*2];
int he[N+M],cnt=0,cur[N+M],dep[N+M],S,T;
void adde(int u,int v,int cap){
    e[cnt]={v,cap,0,he[u]},he[u]=cnt,cnt++,
    e[cnt]={u,0,0,he[v]},he[v]=cnt,cnt++;
}
bool bfs(){
    memset(dep,-1,sizeof(dep));
    queue<int> q; q.push(S),dep[S]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=he[u];i!=-1;i=e[i].ne){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].cap>e[i].flow)
                q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[T]!=-1;
}
int dfs(int u,int f){
    if (u==T||f==0) return f;
    int flow=0;
    for (int &i=cur[u];i!=-1;i=e[i].ne){
        int v=e[i].to,newf;
        if(dep[v]==dep[u]+1&&(newf=dfs(v,min(f,e[i].cap-e[i].flow)))>0){
            e[i].flow+=newf,e[i^1].flow-=newf;
            flow+=newf,f-=newf;
            if(f==0) break;
        }
    }
    return flow;
}
int dinic(){
    int maxFlow=0;
    while(bfs()){
        for(int i=S;i<=T;i++) cur[i]=he[i];
        maxFlow+=dfs(S,INF);
    }
    return maxFlow;
}
int main(){
    int n,m,h=0; cin>>n>>m,S=0,T=n+m+1;
    memset(he,-1,sizeof(he));
    for(int i=1,p;i<=n;i++) cin>>p,adde(i,T,p);
    for(int i=1,a,b,c;i<=m;i++) 
        cin>>a>>b>>c,h+=c,adde(S,n+i,c),
        adde(n+i,a,INF),adde(n+i,b,INF);
    cout<<h-dinic();
    return 0;
}