4240394_ac_2063ms_12280k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <cstring>
#include <climits>
#include <deque>

using namespace std;

const int MAX_VERTEX = 700;

struct Edge {
    int to, cap, flow, cost;
    Edge *next, *rev;

    Edge(int t = 0, int ca = 0, int co = 0, Edge* n = NULL)
        :to(t), cap(ca), cost(co), next(n), flow(0) {}
};

Edge g_mem[MAX_VERTEX * MAX_VERTEX];
int g_allocN = 0;

Edge* newEdge(int t, int ca, int co = 0, Edge* n = NULL)
    { g_mem[g_allocN] = Edge(t, ca, co, n);
      return &g_mem[g_allocN++]; }

class Network {
public:
    void addEdge(int from, int to, int cap, int revCap, int cost = 0) {
        m_adj[from] = newEdge( to,   cap,     cost, m_adj[from] );
        m_adj[to] =   newEdge( from, revCap, -cost, m_adj[to]   );
        m_adj[from]->rev = m_adj[to];  m_adj[to]->rev = m_adj[from];
    }

    void clear() { memset( m_adj, 0, sizeof(m_adj) );
                   g_allocN = 0; }

    void init(int n, int source, int sink)
        { clear();  m_n = n;  m_src = source;  m_snk = sink; }

    int minCost() const { return m_minC; }

    int minCostMaxFlow() {
        int result = 0;
        m_minC = 0;
        while ( findMinCostAugment() ) {
            for (int i = m_snk; i != m_src; i = m_path[i].pre)
                { m_path[i].edge->flow++;
                  m_path[i].edge->rev->flow--; }
            result++;
            m_minC += m_path[m_snk].cost;
        }
        return result;
    }

private:
    struct Path { int pre, cap, cost;
                  Edge* edge; };

    bool findMinCostAugment() {
        for (int i = 0; i < m_n; i++) { m_path[i].pre = -1;
                                        m_path[i].cost = INT_MAX; }
        m_path[m_src].pre = m_src;  m_path[m_src].cost = 0;
        deque<int> que(1, m_src);
        while ( !que.empty() ) {
            int from = que.front();  que.pop_front();
            for (Edge* e = m_adj[from]; e; e = e->next)
                if (e->cap > e->flow) {
                    int cost = m_path[from].cost + e->cost, to = e->to;
                    if (cost < m_path[to].cost) {
                        m_path[to].cost = cost;
                        m_path[to].pre = from;
                        m_path[to].edge = e;
                        if (to != m_snk)  que.push_back(to);
                    }
                }
        }
        return m_path[m_snk].pre != -1;
    }

    Edge* m_adj[MAX_VERTEX];
    int m_n, m_src, m_snk, m_minC;
    Path m_path[MAX_VERTEX];
};

#include <cstdio>
#include <set>

const int MAX_N = 210;
const int MAX_X = 110000;

struct Intv { int l, r, w; };

Intv g_intv[MAX_N];
int g_n;
int g_bnd;
int g_newX[MAX_X + 1];
int g_maxX;
Network g_net;

void input() {
    scanf("%d %d", &g_n, &g_bnd);
    set<int> xs;
    for (int i = 0; i < g_n; i++) {
        scanf("%d %d %d", &g_intv[i].l, &g_intv[i].r, &g_intv[i].w);
        xs.insert( g_intv[i].l );
        xs.insert( g_intv[i].r );
    }
    g_maxX = 0;
    for (set<int>::iterator i = xs.begin(); xs.end() != i; i++)
        g_newX[*i] = g_maxX++;
    for (int i = 0; i < g_n; i++) {
        g_intv[i].l = g_newX[ g_intv[i].l ];
        g_intv[i].r = g_newX[ g_intv[i].r ];
    }
}

void solve() {
    int src = g_maxX;
    g_net.init(g_maxX + 1, src, g_maxX - 1);
    g_net.addEdge(src, 0, g_bnd, 0, 0);
    for (int x = 0; x < g_maxX - 1; x++)
        g_net.addEdge(x, x + 1, g_bnd, 0, 0);
    for (int i = 0; i < g_n; i++)
        g_net.addEdge( g_intv[i].l, g_intv[i].r, 1, 0, -g_intv[i].w );
    int f = g_net.minCostMaxFlow();
    int cost = -g_net.minCost();
    printf("%d\n", cost);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        input();
        solve();
    }
    return 0;
}