BZOJ2055.md

建图跑有源汇上下界最小费用流即可

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 222;
const int INF = 0x3f3f3f3f;

#define S 0
#define T MAXN - 1
#define SS MAXN - 2
#define TT MAXN - 3
int dist[MAXN],flow[MAXN],pre[MAXN],preid[MAXN];
bool vis[MAXN];
struct EDGE{
    int to,cap,fee,rev;
    EDGE(){}
    EDGE(int _to, int _cap, int _fee, int _rev){
        to = _to; cap = _cap;
        fee = _fee; rev = _rev;
    }
};
vector<EDGE> G[MAXN];
void ADDEDGE(int u, int v, int cap, int fee){
    G[u].emplace_back(EDGE(v,cap,fee,(int)G[v].size()));
    G[v].emplace_back(EDGE(u,0,-fee,(int)G[u].size()-1));
}
bool spfa(){
    memset(dist,0x3f,sizeof(dist));
    dist[SS] = 0;
    flow[SS] = INF;
    memset(vis,0,sizeof(vis));
    queue<int> que;
    que.push(SS);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for(int i = 0; i < (int)G[u].size(); i++){
            auto e = G[u][i];
            if(!e.cap or dist[e.to]<=dist[u]+e.fee) continue;
            dist[e.to] = dist[u] + e.fee;
            flow[e.to] = min(e.cap,flow[u]);
            pre[e.to] = u; preid[e.to] = i;
            if(!vis[e.to]){
                vis[e.to] = 1;
                que.push(e.to);
            }
        }
    }
    return dist[TT]!=INF;
}
int mcmf(){
    int cost = 0;
    while(spfa()){
        int u = TT;
        cost += dist[TT] * flow[TT];
        while(u!=SS){
            int p = pre[u], id = preid[u];
            G[p][id].cap -= flow[TT];
            G[u][G[p][id].rev].cap += flow[TT];
            u = pre[u];
        }
    }
    return cost;
}
int n,m;
int d[MAXN][MAXN],c[MAXN];
int main(){
    ____();
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) cin >> d[i][j];
    for(int i = 1; i <= n; i++) ADDEDGE(SS,i+n,c[i],0), ADDEDGE(i,TT,c[i],0);
    ADDEDGE(SS,2*n+1,m,0);
    ADDEDGE(S,TT,m,0);
    ADDEDGE(2*n+1,T,INF,0);
    ADDEDGE(T,S,INF,0);
    for(int i = 1; i <= n; i++) ADDEDGE(2*n+1,i,INF,0), ADDEDGE(i+n,T,INF,0);
    for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if(d[i][j]!=-1) ADDEDGE(i+n,j,INF,d[i][j]);
    cout << mcmf() << endl;
    return 0;
}