发布时间：2024-07-31

有源汇上下界费用流

这里的费用流不需要满流，只需要符合条件就行

步骤：

先把原图的边连了
然后汇点 $t$ 向 $s$ 连 $(0,\infty ,0)$
计算每个点的流入流出 $F_i$
$F_i \gt 0$ ,附加源点 $S$ 向 $i$ 连 $(0,F_i,0)$
否则， $i$ 向附加汇点 $T$ 连 $(0,-F_i,0)$
原图可行费用流=新图最大流费用流+ $\sum Low_i \cdot w_i$ （即该条边的下界*该条边的费用）

cpp

int h[N],e[M],f[M],w[M],ne[M],Low[M],idx;
int dis[N],cur[N];//d表示最短距离,cur为当前弧
int n,m,S,T;
bool vis[N];
int height[N];// 势能函数
vector<int> dot;// 点数
void add(int a,int b,int c,int d,int val){
    e[idx]=b,f[idx]=d-c,w[idx]=val,Low[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-val,ne[idx]=h[b],h[b]=idx++;
}
bool dijk(){
    for(auto &i:dot)dis[i]=INF,cur[i]=h[i];
	priority_queue<PII,vector<PII>,greater<>> pq;
	dis[S]=0;
    pq.emplace(0,S);
    while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(dis[u]!=d)continue;
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
				dis[v]=d+height[u]-height[v]+w[i];
				pq.emplace(dis[v],v);
			}
		}
    }
    return dis[T]!=INF;
}   
int find(int u,int limit){
	if(!limit||u==T)return limit;
	int flow=0;
	vis[u]=1;
    for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
        int v=e[i];
        if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
            int t=find(v,min(f[i],limit-flow));
            f[i]-=t,f[i^1]+=t,flow+=t;
			if(flow==limit)break;
        }
    }
	vis[u]=0;
    return flow;
}
void mcmf(int &flow,int &cost){
	flow=cost=0;
	int r;
    for(auto &i:dot)height[i]=0;
	while(dijk()){
		int r=find(S,INF);
		flow+=r;
		for(auto &i:dot)height[i]+=dis[i];
		cost+=height[T]*r;
	}
}
void clear(){
    for(auto &i:dot)h[i]=-1;
    dot.clear();
    for(int i=0;i<idx;i++)e[i]=f[i]=w[i]=ne[i]=Low[i]=0;
    idx=0;
}
void solve() {
    clear();
    cin>>n>>m;
    int s=0,t=m+2*n+2;
    S=m+2*n+3,T=m+2*n+4;
    vector<int> F(m+2*n+3);// 出入
    for(int i=0;i<=m+2*n+4;i++)dot.push_back(i);
    for(int i=1;i<=m;i++){
        int l;
        cin>>l;
        add(s,i,l,INF,0);
        F[s]-=l,F[i]+=l;
    }
    vector<int> c(2*n+1),v(2*n+1);
    for(int i=1;i<=2*n;i++)cin>>c[i];
    for(int i=1;i<=2*n;i++)cin>>v[i];
    for(int i=1;i<=2*n;i++){
        add(c[i],i+m,0,1,-v[i]);
        add(i+m,i+m+1,(i+1)/2,INF,0);
        F[i+m]-=(i+1)/2,F[i+m+1]+=(i+1)/2;
    }
    add(m+2*n+1,t,n,n,0);
    F[m+2*n+1]-=n,F[t]+=n;
    int tot=0;
    for(int i=0;i<=m+2*n+2;i++){
        if(F[i]>0)add(S,i,0,F[i],0),tot+=F[i];
        else add(i,T,0,-F[i],0);
    }
    add(t,s,0,INF,0);
    int flow,cost;
    mcmf(flow,cost);
    // cout<<flow<<" "<<cost<<"\n";
    if(flow!=tot){
        cout<<"-1\n";
        return;
    }
    int res=-cost;
    for(int i=0;i<idx;i+=2){
        res+=Low[i]*w[i];
    }
    cout<<res<<"\n";
}

有源汇上下界费用流 ​

有源汇上下界费用流