有源汇上下界最小费用流（可行流与最大流）

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge{
    int u,v,nxt,f,w;
}edge[maxn<<1];
int head[255],cnt = -1;
int w[255];
int sb[55][55],sw[55][55];
int L[55],R[55],l[55],r[55];
inline void add_edge(int u,int v,int f,int w){
    edge[++cnt] = {u,v,head[u],f,w};
    head[u] = cnt;
    edge[++cnt] = {v,u,head[v],0,-w};
    head[v] = cnt;
}
inline void init(){
    memset(head,-1,sizeof(head));   cnt = -1;
}
int dis[255],flow[255],vis[255],pre[255],last[255];
bool spfa(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    memset(flow,0x3f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    queue<int> q;   q.push(s);
    vis[s] = 1,dis[s] = 0,pre[t] = -1;
    while(!q.empty()){
        int u = q.front();  q.pop();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = edge[i].nxt){
            Edge &e = edge[i];
            if(e.f > 0 && dis[e.v] > dis[u] + e.w){
                dis[e.v] = dis[u] + e.w;
                pre[e.v] = u;
                last[e.v] = i;
                flow[e.v] = min(flow[u],e.f);
                if(!vis[e.v]){
                    vis[e.v] = 1;
                    q.push(e.v);
                }
            }
        }
    }
    return pre[t] != -1;
}
int maxflow,mincost;
int MCMF(int s,int t){
    maxflow = mincost = 0;
    while(spfa(s,t)){
        int u = t;
        maxflow += flow[t];
        mincost += flow[t] * dis[t];
        while(u != s){
            edge[last[u]].f -= flow[t];
            edge[last[u]^1].f += flow[t];
            u = pre[u];
        }
    }
    return maxflow;
}
int main(){
    IOS;
    init();
    int n,m;    cin >> n >> m;
    int s = 0, t = n + m + 1;
    int ss = t + 1,tt = ss + 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> sb[i][j];
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> sw[i][j];
        }
    }
    //下面输入上下限
    for(int i = 1; i <= n; ++i){
        cin >> l[i] >> r[i];
    }
    for(int i = 1; i <= m; ++i){
        cin >> L[i] >> R[i];
    }
    //下面是建边求可行流
    for(int i = 1; i <= n; ++i){
        add_edge(s, i, r[i]-l[i], 0);
        w[s] -= l[i];   w[i] += l[i];
    }
    for(int i = 1; i <= m; ++i){
        add_edge(i + n, t, R[i] - L[i], 0);
        w[i+n] -= L[i]; w[t] += L[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            add_edge(j + n, i, 1, sw[i][j]);
            add_edge(i, j + n, 1, sb[i][j]);//最小循环流满流处理
        }
    }
    //下面是补全流
    long long sum = 0;
    for(int i = 0; i <= t; ++i){
        if(w[i] > 0){
            add_edge(ss, i, w[i], 0);
            sum += w[i];
        }else if(w[i] <= 0){
            add_edge(i, tt, -w[i], 0);
        }
    }
    add_edge(t, s, INF, 0);

    //上下限没有负限制的时候不需要加这个add(s,t,INF,0)，而这里不加只能通过牛客69%的数据)
    add_edge(s, t, INF, 0);
    MCMF(ss,tt);
    //MCMF(s,t);
    cout <<mincost << endl;
    return 0;
}