有源汇上下界最小费用流（可行流与最大流）
<pre><code class="language-cpp">#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;
}
</code></pre>