有源汇最小费用流（可行流与最大流）
<pre><code class="language-cpp">//可行流保证钱最少，最大流保证流最大
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef int ll;
typedef pair<ll, int> P;
const int maxn = 5005;
const int maxm = maxn * maxn * 2;
const ll INF = 0x3f3f3f3f;
struct Edge{
int to;
int next;
ll cap;
ll cost;
};
Edge edge[maxm];
int head[maxn];
int tol;
int n, m;
void init(){
tol = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, ll ca, ll co, ll rca = 0){
edge[tol].to = v;
edge[tol].cap = ca;
edge[tol].cost = co;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rca;
edge[tol].cost = -co;
edge[tol].next = head[v];
head[v] = tol++;
}
namespace Vflows{
int h[maxn], prevv[maxn], preve[maxn];
ll dist[maxn];
pair<ll, ll> min_cost_flow(int s, int t, int n){//源点，汇点，点的个数
ll res = 0, ans = 0;//res费用，ansflow
for(int i = 1; i <= n; i++) h[i] = 0;
while(233){
priority_queue<P, vector<P>, greater<P> >que;
for(int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;
que.push(P(0, s));
while(que.size()){
P p = que.top();
que.pop();
int v = p.second;
if(dist[v] < p.first) continue;
for(int i = head[v]; ~i; i = edge[i].next){
Edge &e = edge[i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to], e.to));
}
}
}
if(dist[t] == INF) break;
for(int i = 1; i <= n; i++) h[i] += dist[i];
ll d = INF;
for(int i = t; i != s; i = prevv[i]){
d = min(d, edge[preve[i]].cap);
}
res += d * h[t];
ans += d;
for(int i = t; i != s; i = prevv[i]){
edge[preve[i]].cap -= d;
edge[preve[i]^1].cap += d;
}
}
return make_pair(res, ans);
}
}
int num[maxn];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &num[i]);
}
init();
int s = n+1, t = n+2;
for(int i = 1; i <= n; i++){
if(num[i] == 1) addedge(s, i, 1, 0);
else addedge(i, t, 1, 0);
if(num[i] == 0) continue;
for(int j = 1; j <= n; j++){
if(i == j || num[j] == 1) continue;
addedge(i, j, 1, max(i, j) - min(i, j));
}
}
pair<ll, ll> p = Vflows::min_cost_flow(s, t, n+2);
cout << p.first;
}
</code></pre>