// LibreOJ #102. 最小费用流
#include <bits/stdc++.h>

using ll = long long;
const ll INF = 1ll<<60;
const int MaxN = 405;

struct Edge { int to, twin; ll cap, cost; };
std::vector<Edge> g[MaxN];
void addEdge(int u, int v , ll cap, ll cost) {
    g[u].push_back((Edge){v, g[v].size(), cap, cost});
    g[v].push_back((Edge){u, g[u].size()-1, 0, -cost});
}
int n, m, S, T, pre[MaxN];
Edge *preEdge[MaxN];
ll dis[MaxN];
bool in[MaxN];
ll spfa() {
    std::fill(dis+1, dis+n+1, INF);
    std::queue<int> q;
    q.push(S);
    dis[S] = 0;
    while(!q.empty()) {
        int u = q.front();
        in[u] = false;
        q.pop();
        for (Edge &e : g[u]) {
            if (e.cap == 0) continue;
            int v = e.to;
            if (dis[v] > dis[u]+e.cost) {
                dis[v] = dis[u]+e.cost;
                pre[v] = u;
                preEdge[v] = &e;
                if (!in[v]) {
                    in[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dis[T];
}
void maxflow(ll &flow, ll &cost) {
    while(true) {
        ll dis = spfa();
        if (dis == INF) break;
        ll f0 = INF;
        for (int v=T; v!=S; v=pre[v]) {
            Edge &preE = *preEdge[v];
            f0 = std::min(f0, preE.cap);
        }
        flow += f0;
        cost += f0*dis;
        for (int v=T; v!=S; v=pre[v]) {
            Edge &preE = *preEdge[v];
            preE.cap -= f0;
            g[v][preE.twin].cap += f0;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    S = 1; T = n;
    for (int i=1; i<=m; i++) {
        int u, v, cap, cost;
        scanf("%d%d%d%d", &u, &v, &cap, &cost);
        addEdge(u, v, cap, cost);
    }
    ll flow = 0, cost = 0;
    maxflow(flow, cost);
    printf("%lld %lld", flow, cost);
    return 0;
}

D23 网络流 费用流 EK 算法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL N=5010,M=110000;
struct edge{int x,y;LL f,c;int pre;}a[M];int alen,last[N];
void ins(int x,int y,LL f,LL c)
{
    a[++alen]={x,y,f,c,last[x]};last[x]=alen;
}

int n,m,st,ed;LL d[N],mf[N],pre[N],vis[N];
bool spfa()
{
    queue<int> q;
    memset(d,0x0f,sizeof(d));d[st]=0;
	memset(mf,0,sizeof(mf));mf[st]=LL(1)<<50;
    memset(vis,0,sizeof(vis));
    q.push(st);vis[st]=1;
    while(!q.empty())
	{
        LL x=q.front();q.pop();vis[x]=0;
        for(int k=last[x];k;k=a[k].pre)if(a[k].f>0)
		{
            int y=a[k].y;
            if(d[y]>d[x]+a[k].c)
			{
                d[y]=d[x]+a[k].c;
				pre[y]=k;
				mf[y]=min(mf[x],a[k].f);
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }    
    }
    return d[ed]!=d[0];
}
   
int main()
{
    scanf("%d%d",&n,&m);st=1;ed=n;
	alen=1;memset(last,0,sizeof(last));
    for(int i=1;i<=m;i++)
	{
        int x,y;LL f,c;scanf("%d%d%lld%lld",&x,&y,&f,&c);
        ins(x,y,f,c);
		ins(y,x,0,-c);
    }
    LL flow=0,cost=0;
    while(spfa())
	{
        for(int v=ed;v!=st;){
			int i=pre[v];
			a[i].f-=mf[ed];
			a[i^1].f+=mf[ed];
			v=a[i^1].y;
		}
        flow+=mf[ed];
		cost+=d[ed]*mf[ed];
    }
    printf("%lld %lld",flow,cost);
    return 0;
}