ACM模板库

ACM模板库


有源汇最小费用流(可行流与最大流)

//可行流保证钱最少,最大流保证流最大
#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;
}

页面列表

ITEM_HTML