如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。
输入格式
第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。
输出格式
一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。
输入输出样例
说明/提示
时空限制: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。
思路:初学费用流,找到了一篇不错的教程,思路是利用最短路保证最小费用,再在最大流的基础上,算出最大流的最小的费用,似乎可以把sfpa换成dijkstra?
AC代码:
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;
struct unit
{
int to;//指向
int f;//流量
int w;//单位花费
int rev;//反向边序号
unit() {};
unit(int n, int ff, int ww, int r) :to(n), f(ff), w(ww), rev(r) {};
};
vector<unit> G[50001];
int cur[50001];
int dis[50001];
bool v[50001];
int n, m, st, ed;
int maxflow, mincost;
void add(int x, int y, int f, int w)//建边
{
G[x].push_back(unit(y, f, w, G[y].size()));
G[y].push_back(unit(x, 0, -w, G[x].size() - 1));//反向边,流量为0,单位花费为负
}
bool spfa()//标准SPFA
{
ffor(i, 1, n)
{
v[i] = false;
dis[i] = IMAX;
}
dis[st] = 0;
queue<int> q;
q.push(st);
while (!q.empty())
{
int f = q.front();
q.pop();
v[f] = false;
for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
{
unit u = *it;
if (u.f && dis[f] + u.w < dis[u.to])
{
dis[u.to] = dis[f] + u.w;
if (!v[u.to])
{
q.push(u.to);
v[u.to] = true;
}
}
}
}
return dis[ed] != IMAX;//能走到就返回
}
int dfs(int x, int f)
{
if (x == ed)
return f;
v[x] = true;//防止重复走
int sum = 0;
for (int& i = cur[x]; i <= G[x].size() - 1; i++)
{
unit& u = G[x][i];
if (!v[u.to] && u.f && dis[u.to] == dis[x] + u.w)
{
int flow = dfs(u.to, min(f - sum, u.f));
if (flow)//确认可以流通,就对边进行操作,记录最大流和最小花费
{
sum += flow;
u.f -= flow;
G[u.to][u.rev].f += flow;
mincost += u.w * flow;
if (sum == f)break;
}
}
}
v[x] = false;
return sum;
}
void dinic()
{
while (spfa())
{
mes(cur, 0);
maxflow += dfs(st, IMAX);
}
}
signed main()
{
cin >> n >> m >> st >> ed;
maxflow = mincost = 0;
ffor(i, 1, m)
{
int x, y, w, c;
scanf("%lld%lld%lld%lld", &x, &y, &w, &c);
add(x, y, w, c);
}
dinic();
printf("%lld %lld\n", maxflow, mincost);
}