【模板】最小费用最大流

题目描述

如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。

输入输出格式

输入格式：

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。

输出格式：

一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

50 280

说明

时空限制：1000ms,128M

（BYX：最后两个点改成了1200ms）

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=1000，M<=1000

对于100%的数据：N<=5000，M<=50000

样例说明：

【模板】最小费用最大流

如图，最优方案如下：

第一条流为4-->3，流量为20，费用为3*20=60。

第二条流为4-->2-->3，流量为20，费用为（2+1）*20=60。

第三条流为4-->2-->1-->3，流量为10，费用为（2+9+5）*10=160。

故最大流量为50，在此状况下最小费用为60+60+160=280。

故输出50 280。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize("O3")
using namespace std;
#define maxn 200005
#define inf 0x3f3f3f3f
#define INF 999999999999999
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long  ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const int mod = 10000007;
#define Mod 20100403
#define sq(x) (x)*(x)
#define eps 1e-5
typedef pair<int, int> pii;
#define pi acos(-1.0)
const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
inline int rd() {
    int x = 0;
    char c = getchar();
    bool f = false;
    while (!isdigit(c)) {
        if (c == '-') f = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f ? -x : x;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}
ll sqr(ll x) { return x * x; }

bool vis[maxn];
int n, m, s, t;
int x, y, f, z;
int dis[maxn], pre[maxn], last[maxn], flow[maxn];
int maxflow, mincost;

struct node {
    int to, nxt, flow, dis;
}edge[maxn<<2];

int head[maxn], cnt;
queue<int>q;

void addedge(int from, int to, int flow, int dis) {
    edge[++cnt].to = to; edge[cnt].flow = flow; edge[cnt].dis = dis;
    edge[cnt].nxt = head[from]; head[from] = cnt;
}

bool spfa(int s, int t) {
    memset(dis, 0x7f, sizeof(dis)); memset(flow, 0x7f, sizeof(flow));
    ms(vis);
    q.push(s); vis[s] = 1; dis[s] = 0; pre[t] = -1;
    while (!q.empty()) {
        int now = q.front(); q.pop(); vis[now] = 0;
        for (int i = head[now]; i != -1; i = edge[i].nxt) {
            if (edge[i].flow > 0 && dis[edge[i].to] > dis[now] + edge[i].dis) {
                dis[edge[i].to] = edge[i].dis + dis[now];
                pre[edge[i].to] = now; last[edge[i].to] = i;
                flow[edge[i].to] = min(flow[now], edge[i].flow);
                if (!vis[edge[i].to]) {
                    vis[edge[i].to] = 1; q.push(edge[i].to);
                }
            }
        }
    }
    return pre[t] != -1;
}

void mincost_maxflow() {
    while (spfa(s, t)) {
        int now = t;
        maxflow += flow[t]; mincost += flow[t] * dis[t];
        while (now != s) {
            edge[last[now]].flow -= flow[t];
            edge[last[now] ^ 1].flow += flow[t];
            now = pre[now];
        }
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    memset(head, -1, sizeof(head)); cnt = 1;
    rdint(n); rdint(m); rdint(s); rdint(t);
    for (int i = 1; i <= m; i++) {
        rdint(x); rdint(y); rdint(z); rdint(f);
        addedge(x, y, z, f); addedge(y, x, 0, -f);
    }
    mincost_maxflow();
    cout << maxflow << ' ' << mincost << endl;
    return 0;
}

【模板】最小费用最大流

题目描述

输入输出格式

输入输出样例

说明

相关推荐