Codeforces 362E Petya and Pipes （费用流） - c++编程基础

n个点的网络，可以增加某些弧的容量，最大增加量为K，求增加后的最大流。

要求增大K容量后的最大流，那如果把增加的流量加上费用呢？那题目也就是说，当费用为K的时候，最大流是多少。。。。

把每条边拆成两条边跟，然后求s-t费用流，在费用等于K的时候终止费用流就行了。

#include  
#include  
#include  
#include  
#include  
#define REP(i, n) for(int i=0; i G[maxn];  
    vector edges;  
    bool inq[maxn];  
    int p[maxn], a[maxn], d[maxn];  
  
    void AddEdge(int from, int to, int cap, int cost)  
    {  
        Edge e1 = Edge(from, to, cap, 0, cost);  
        Edge e2 = Edge(to, from, 0, 0, -cost);  
        edges.PB(e1); edges.PB(e2);  
        m = edges.size();  
        G[from].PB(m-2); G[to].PB(m-1);  
    }  
  
    bool spfa(int s, int t, int& flow, int& cost)  
    {  
        CLR(inq, 0);  
        REP(i, n) d[i] = INF;  
        d[s] = p[s] = 0; a[s] = INF;  
        queue q; q.push(s);  
        while(!q.empty())  
        {  
            int u = q.front(); q.pop();  
            inq[u] = false;  
            REP(i, G[u].size())  
            {  
                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];  
                    a[e.to] = min(a[u], e.cap - e.flow);  
                    if(!inq[e.to])  
                    {  
                        q.push(e.to);  
                        inq[e.to] = true;  
                    }  
                }  
            }  
        }  
        if(d[t] == INF) return false;  
        if(cost + d[t] * a[t] > K)  
        {  
            flow += (K - cost) / d[t];  
            return false;  
        }  
        cost += d[t] * a[t];  
        flow += a[t];  
        int u = t;  
        while(u != s)  
        {  
            edges[p[u]].flow += a[t];  
            edges[p[u]^1].flow -= a[t];  
            u = edges[p[u]].from;  
        }  
        return true;  
    }  
  
    int Mincost(int s, int t, int& flow, int& cost)  
    {  
        this->n = t + 1;  
        flow = cost = 0;  
        while(spfa(s, t, flow, cost));  
        return flow;  
    }  
}solver;  
  
int main()  
{  
    scanf("%d%d", &n, &K);  
    REP(i, n) REP(j, n)  
    {  
        scanf("%d", &x);  
        if(x)  
        {  
            solver.AddEdge(i, j, x, 0);  
            solver.AddEdge(i, j, K, 1);  
        }  
    }  
    int flow, cost;  
    printf("%d\n", solver.Mincost(0, n-1, flow, cost));  
    return 0;  
}