UVA - 11613 Acme Corporation(最小費用流)

UVA - 11613 Acme Corporation(最小費用流)

題目大意：A公司生產一種元素，給出該元素在未來M個月中每個月的單位售價，最大生產量，生產成本，最大銷售量和最大存儲時間，和每月存儲代價，問這家公司在M個月內所能賺大的最大利潤

解題思路：這題建圖還是比較簡單的。主要說一下怎麼跑出答案吧。我用的是MCMF，建邊的時候，費用我用的是相反數，所以得到最小費用後要去相反數
MCMF的時候，用一個數組紀錄了到達匯點時所花費的最小價值，因為取的是相反數，所以當價值為正時，就表示已經虧本了，所以可以退出了

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 1010
#define ll long long
#define abs(a)((a)>0?(a):(-(a)))
#define INF 0x3f3f3f3f3f3f3f3f

struct Edge{
    int from, to;
    ll cap, flow ,cost;
    Edge() {}
    Edge(int from, int to, ll cap, ll flow, ll cost):from(from), to(to), cap(cap), flow(flow), cost(cost) {}
};

struct MCMF{
    int n, m, source, sink;
    vector edges;
    vector G[N];
    ll d[N], f[N];
    int  p[N];
    bool vis[N];

    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; i++)
            G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, ll cap, ll cost) {
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BellmanFord(int s, int t, ll &flow, ll &cost) {
        for (int i = 0; i <= n; i++)
            d[i] = INF;
        memset(vis, 0, sizeof(vis));
        vis[s] = 1; d[s] = 0; f[s] = INF; p[s] = 0;
        queue Q;
        Q.push(s);

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            vis[u] = 0;

            for (int i = 0; i < G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    f[e.to] = min(f[u], e.cap - e.flow);
                    if (!vis[e.to]) {
                        vis[e.to] = true;
                        Q.push(e.to);
                    }
                }
            }
        }

        if (d[t] > 0)
            return false;

        flow += f[t];
        cost += d[t] * f[t];

        int u = t;
        while (u != s) {
            edges[p[u]].flow += f[t];
            edges[p[u] ^ 1].flow -= f[t];
            u = edges[p[u]].from;
        }
        return true;
    }

    ll Mincost(int s, int t) {
        ll flow = 0, cost = 0;
        while (BellmanFord(s, t, flow, cost));
        return cost;
    }
};
MCMF mcmf;
int n, m, source, sink, cas = 1;

struct Node{    
    ll m, n, p, s, e;
}node[N];

void init() {
    scanf(%d%d, &n, &m);
    source = 0; sink = 2 * n + 1;
    mcmf.init(sink);
    for (int i = 1; i <= n; i++) { 
        scanf(%lld%lld%lld%lld%lld, &node[i].m, &node[i].n, &node[i].p, &node[i].s, &node[i].e);
        mcmf.AddEdge(source, i, node[i].n, 0);
        mcmf.AddEdge(i + n, sink, node[i].s, 0);
    }

    for (int i = 1; i <= n; i++) {
        mcmf.AddEdge(i, i + n, INF, node[i].m - node[i].p);
        for (int j = 1; j <= node[i].e && i + j <= n; j++) 
            mcmf.AddEdge(i, i + j + n, INF, m * j + node[i].m - node[i+j].p);
    }
    ll ans = mcmf.Mincost(source, sink);
    printf(Case %d: %lld
, cas++, abs(ans));
}

int main() {
    int test;
    scanf(%d, &test);
    while (test--) {
        init();
    }
    return 0;
}