洛谷 3381: 【模板】最小费用最大流

2018-03-27Chentiancai_nn?

题目描述

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出样例#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\times 20=60$。

第二条流为4–>2–>3,流量为20,费用为$(2+1)\times 20=60$。

第三条流为4–>2–>1–>3,流量为10,费用为$(2+9+5)\times 10=160$。

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

故输出50 280。

题解

是一道板子题,事实上只是来存代码的

代码

这是zkw费用流的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int N = 5005,M = 50005,INF = 1e9;
bool vis[N];int dist[N];
int n,m,s,t,ans = 0;
int cnt = -1,to[M*2],head[N],nxt[M*2],w[M*2],val[M*2];
inline void insert(int x,int y,int z,int k){ to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; w[cnt] = z; val[cnt] = k; }
inline bool spfa(int s,int t){
memset(vis,0,sizeof vis);
for(int i = 0;i <= n;++i) dist[i] = INF;
dist[t] = 0; vis[t] = 1;
deque<int> Q; Q.push_back(t);
do{
int x = Q.front(); Q.pop_front();
for(int i = head[x];i != -1;i = nxt[i])
if(w[i^1] > 0 && dist[to[i]] > dist[x]-val[i]){
dist[to[i]] = dist[x]-val[i];
if(!vis[to[i]]){
vis[to[i]] = true;
if(!Q.empty() && dist[to[i]] < dist[Q.front()]) Q.push_front(to[i]);
else Q.push_back(to[i]);
}
}
vis[x] = 0;
}while(!Q.empty());
return dist[s] < INF;
}
inline int dfs(int x,int flow){
vis[x] = true;
if(x == t) return flow;
for(int i = head[x];i != -1;i = nxt[i])
if(!vis[to[i]] && w[i] && dist[to[i]] == dist[x]-val[i]){
int di = dfs(to[i],min(flow,w[i]));
if(di > 0){
w[i] -= di; w[i^1] += di;
ans += di*val[i];
return di;
}
}
return 0;
}

inline void costflow(){
int flow = 0;
while(spfa(s,t)){
do{
memset(vis,0,sizeof vis);
flow += dfs(s,INF);
}while(vis[t]);
}
printf("%d %d\n",flow,ans);
}

int main(){
memset(head,-1,sizeof head);
n = read(); m = read(); s = read(); t = read();
for(int i = 1;i <= m;++i){
int x = read(),y = read(),z = read(),k = read();
insert(x,y,z,k); insert(y,x,0,-k);
} costflow();
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close