dinnerhunt

广工-最大瘤版本

//MCMF->init(N) -> MCMF.add(u,v,flow,cost) -> (flow,cost) = MCMF.run(s,t,UP)  
//其中UP参数表示求s到t的流量不超过UP的情况下的最小费用，无要求填INF即可  
//所有节点的id范围[0,N]  
const int MAXN = 10005;  
const int INF = 0x7fffffff;  
struct MinCostMaxFlow {  
    struct edge {  
        int v, f, c, r;  
        edge(int _v, int _f, int _c, int _r) :v(_v), f(_f), c(_c), r(_r) {}  
    };  
    int V = 0, H[MAXN + 5], dis[MAXN + 5], PreV[MAXN + 5], PreE[MAXN + 5];  
    vector<edge> G[MAXN + 5];  
    inline void init(int n) {  
        for (int i = 0; i <= V; ++i) G[i].clear();  
        V = n;  
    }  
    inline void add(int u, int v, int f, int c) {  
        G[u].push_back(edge(v, f, c, G[v].size()));  
        G[v].push_back(edge(u, 0, -c, G[u].size() - 1));  
    }  
    typedef pair<int, int> P;  
    P run(int s, int t, int f) {  
        int cost = 0, flow = 0, tf; fill(H, H + 1 + V, 0);  
        while (f) {  
            priority_queue <P, vector<P>, greater<P> > q;  
            fill(dis, dis + 1 + V, INF);  
            dis[s] = 0; q.push(P(0, s));  
            while (!q.empty()) {  
                P now = q.top(); q.pop();  
                int v = now.second;  
                if (dis[v] < now.first)continue;  
                for (int i = 0; i < G[v].size(); ++i) {  
                    edge& e = G[v][i];  
                    if (e.f > 0 && dis[e.v] > dis[v] + e.c + H[v] - H[e.v]) {  
                        dis[e.v] = dis[v] + e.c + H[v] - H[e.v];  
                        PreV[e.v] = v, PreE[e.v] = i;  
                        q.push(P(dis[e.v], e.v));  
                    }  
                }  
            }  
            if (dis[t] == INF)break;  
            for (int i = 0; i <= V; ++i) H[i] += dis[i];  
            tf = f;  
            for (int v = t; v != s; v = PreV[v])  
                tf = min(tf, G[PreV[v]][PreE[v]].f);  
            f -= tf, flow += tf, cost += tf*H[t];  
        	for (int v = t; v != s; v = PreV[v]) {  
                edge& e = G[PreV[v]][PreE[v]];  
                e.f -= tf;  
                G[v][e.r].f += tf;  
            }  
        }  
        return P(flow, cost);  
    }  
}MCMF; 

宏版

const ll maxd = 1e5+10;
const ll inf = 1e18;

struct edge{ll to,rev, flow,cost;};
ll n,m,k,num;
vector<edge> G[maxd];
ll h[maxd],dis[maxd],pn[maxd],pe[maxd];

void add(ll u,ll v,ll flow,ll cost)
{
    G[u].push_back((edge){ v,(ll)G[v].size(),flow,cost });
    G[v].push_back((edge){ u,(ll)G[u].size() - 1,0,-cost });
}

void min_cost_flow(ll s,ll t,ll &min_cost,ll &max_flow)
{
    fill(h+1,h+1+num,0);
    min_cost = max_flow = 0;
    ll tot = inf;
    while(tot>0)
    {
        MINQ_P q;
        fill(dis, dis + 1 +  num,inf);
        dis[s] = 0; q.push(P(0ll,s));
        while(!q.empty())
        {
            ll u = q.top().ND,dist = q.top().ST; q.pop();
            if (dis[u] < dist)continue;
            F( G[u].size())
            {
                edge &e = G[u][i];
                if (e.flow > 0 && dis[e.to] > dis[u] + e.cost + h[u] - h[e.to])
                {
                    dis[e.to] = dis[u] +e.cost + h[u] - h[e.to];
                    pn[e.to] = u,pe[e.to] = i;
                    q.push(P(dis[e.to],e.to ));
                }
            }
        }
        if (dis[t] == inf)break;
        // 所有点都要
        FOR(i,0,num) h[i] += dis[i];
        ll flow = tot;
        for (int i = t; i != s; i = pn[i]) flow = min(flow, G[pn[i]][pe[i]].flow);
        for (int i = t; i != s; i = pn[i])
        {
            edge& e = G[pn[i]][pe[i]];
            e.flow -= flow;
            G[i][e.rev].flow += flow;
        }
        tot -= flow;
        max_flow += flow;
        min_cost += flow * h[t];
    }
}
void init(){ FOR(i,1,n+n+3) G[i].clear(); }
ll a[maxd];
int main()
{
    __IN;__OUT;
    ll s, t,T;RLL(T);
    while(T--)
    {
        RLL(n);RLL(m);init(); s = 0 ,t = n+1 , num = t;
        ll min_cost, max_flow;
        min_cost_flow(s, t, min_cost, max_flow);
        PLN(-min_cost);
    }
    return 0;
}