洛谷P2604 网络扩容 拆点+费用流

原题链接

这题貌似比较水吧，最简单的拆点，直接上代码了。

#include <bits/stdc++.h>

using namespace std;

#define N 1000

#define M 5000

#define INF 0x3f3f3f3f

#define mp make_pair

#define pii pair<int, int>

#define pb push_back

int n, m, K, S, T;

int d[2*N+5], vis[2*N+5], a[2*N+5], pre[2*N+5];

int t1[M+5], t2[M+5], t3[M+5], t4[M+5];

struct Edge

{

    int from, to, cap, flow, cost;

};

vector<Edge> edges;

vector<int> G[2*N+5];

void addEdge(int u, int v, int cap, int cost)

{

    edges.pb(Edge{u, v, cap, 0, cost}), edges.pb(Edge{v, u, 0, 0, -cost});

    G[u].pb(edges.size()-2), G[v].pb(edges.size()-1);

}

int SPFA(int &flow, int &cost)

{

    memset(d, 0x3f, sizeof d);

    d[S] = 0, vis[S] = 1, pre[S] = 0, a[S] = INF;

    queue<int> q;

    q.push(S);

    while(!q.empty())

    {

        int u = q.front(); q.pop();

        vis[u] = 0;

        for(int i = 0, v; 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;

                pre[e.to] = G[u][i];

                a[e.to] = min(a[u], e.cap-e.flow);

                if(!vis[e.to]) vis[e.to] = 1, q.push(e.to);

            }

        }

    }

    if(d[T] == INF) return 0;

    flow += a[T], cost += d[T]*a[T];

    int u = T;

    while(u != S)

    {

        edges[pre[u]].flow += a[T], edges[pre[u]^1].flow -= a[T];

        u = edges[pre[u]].from;

    }

    return 1;

}

pii minCost()

{

    int flow = 0, cost = 0;

    while(SPFA(flow, cost));

    return mp(flow, cost);

}

void clear()

{

    for(int i = 0; i <= n; ++i) G[i].clear();

    edges.clear();

}

int main()

{

    scanf("%d%d%d", &n, &m, &K);

    for(int i = 1; i <= m; ++i)

    {

        scanf("%d%d%d%d", &t1[i], &t2[i], &t3[i], &t4[i]);

        addEdge(t1[i], t2[i], t3[i], 0);

    }

    S = 0, T = n;

    addEdge(S, 1, INF, 0);

    int ans1;

    printf("%d ", ans1 = minCost().first);

    clear();

    addEdge(S, 1, ans1+K, 0);

    for(int i = 1; i <= n; ++i) addEdge(i, i+n, INF, 0);

    for(int i = 1; i <= m; ++i)

        addEdge(t1[i], t2[i], t3[i], 0), addEdge(t1[i]+n, t2[i], K, t4[i]);

    printf("%d\n", minCost().second);

    return 0;

}