poj 2135 有流量限制的最小费用最大流

90 阅读 0 评论 60 点赞

我是靠谱客的博主俭朴大白，这篇文章主要介绍poj 2135 有流量限制的最小费用最大流，现在分享给大家，希望可以做个参考。

题意：

农场里有n块地，其中约翰的家在1号地，二n号地有个很大的仓库。

农场有M条道路（双向），道路i连接着ai号地和bi号地，长度为ci。

约翰希望按照从家里出发，经过若干块地后到达仓库，然后再返回家中的顺序带朋友参观。

如果要求往返不能经过同一条路两次，求参观路线总长度的最小值。

解析：

如果只考虑去或者回的情况，问题只不过是无向图中两点之间的最短路问题。

但是现在要去要回，并且不能经过相同的道路，这样。

如果先计算去时最短路，再计算回来时最短路，是不行的。（dp思想）

所以，来求从1号顶点到n号顶点的两条没有公共边的路径。

所以，把顶点之间连接一条流量为1，费用为路程的边。

这样转换之后，就是流量为2的最小费用流了。

敲了n遍有流量限制的网络流，终于a了。。。

代码：

复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1
using namespace std;
const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
//firs - 最短距离
second 顶点编号
typedef pair<int, int> P;
struct Edge
{
int to, cap, cost, rev;
Edge(){}
Edge(int _to, int _cap, int _cost, int _rev)
{
to = _to;
cap = _cap;
cost = _cost;
rev = _rev;
}
};
int V;//顶点数
vector<Edge> g[maxn];
//图的邻接表
int h[maxn];
//残量
int dist[maxn];
//最短距离
int preV[maxn], preE[maxn]; //前驱节点 以及对于的边
//向图中增加一条从fr到to容量为cap费用为cost的边
void addEdge(int fr, int to, int cap, int cost)
{
g[fr].push_back(Edge(to, cap, cost, g[to].size()));
g[to].push_back(Edge(fr, 0, -cost, g[fr].size() - 1));
}
//求解从s到t流量为f的最小费用流
//没有流量为f的流，返回-1
int minCostFlow(int s, int t, int f)
{
int res = 0;
memset(h, 0, sizeof(h));
while (f > 0)
{
priority_queue<P, vector<P>, greater<P> > q;
memset(dist, inf, sizeof(dist));
dist[s] = 0;
q.push(P(0, s));
while (!q.empty())
{
P now = q.top();
q.pop();
int v = now.second;
if (dist[v] < now.first)
continue;
for (int i = 0; i < g[v].size(); i++)
{
Edge& e = g[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
{
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
preV[e.to] = v;
preE[e.to] = i;
q.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == inf)
{
return -1;
}
for (int v = 0; v < V; v++)
h[v] += dist[v];
int d = f;
for (int v = t; v != s; v = preV[v])
{
d = min(d, g[preV[v]][preE[v]].cap);
}
f -= d;
res += d * h[t];
for (int v = t; v != s; v = preV[v])
{
Edge& e = g[preV[v]][preE[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif // LOCAL
int n, m;
while (~scanf("%d%d", &n, &m))
{
V = n;
for (int i = 0; i < n; i++)
{
g[i].clear();
}
int s = 0, t = n - 1;
while (m--)
{
int fr, to, w;
scanf("%d%d%d", &fr, &to, &w);
fr--, to--;
addEdge(fr, to, 1, w);
addEdge(to, fr, 1, w);
}
printf("%dn", minCostFlow(s, t, 2));
}
return 0;
}

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1
using namespace std;
const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
//firs - 最短距离
second 顶点编号
typedef pair<int, int> P;
struct Edge
{
int to, cap, cost, rev;
Edge(){}
Edge(int _to, int _cap, int _cost, int _rev)
{
to = _to;
cap = _cap;
cost = _cost;
rev = _rev;
}
};
int V;//顶点数
vector<Edge> g[maxn];
//图的邻接表
int h[maxn];
//残量
int dist[maxn];
//最短距离
int preV[maxn], preE[maxn]; //前驱节点 以及对于的边
//向图中增加一条从fr到to容量为cap费用为cost的边
void addEdge(int fr, int to, int cap, int cost)
{
g[fr].push_back(Edge(to, cap, cost, g[to].size()));
g[to].push_back(Edge(fr, 0, -cost, g[fr].size() - 1));
}
//求解从s到t流量为f的最小费用流
//没有流量为f的流，返回-1
int minCostFlow(int s, int t, int f)
{
int res = 0;
memset(h, 0, sizeof(h));
while (f > 0)
{
priority_queue<P, vector<P>, greater<P> > q;
memset(dist, inf, sizeof(dist));
dist[s] = 0;
q.push(P(0, s));
while (!q.empty())
{
P now = q.top();
q.pop();
int v = now.second;
if (dist[v] < now.first)
continue;
for (int i = 0; i < g[v].size(); i++)
{
Edge& e = g[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
{
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
preV[e.to] = v;
preE[e.to] = i;
q.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == inf)
{
return -1;
}
for (int v = 0; v < V; v++)
h[v] += dist[v];
int d = f;
for (int v = t; v != s; v = preV[v])
{
d = min(d, g[preV[v]][preE[v]].cap);
}
f -= d;
res += d * h[t];
for (int v = t; v != s; v = preV[v])
{
Edge& e = g[preV[v]][preE[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif // LOCAL
int n, m;
while (~scanf("%d%d", &n, &m))
{
V = n;
for (int i = 0; i < n; i++)
{
g[i].clear();
}
int s = 0, t = n - 1;
while (m--)
{
int fr, to, w;
scanf("%d%d%d", &fr, &to, &w);
fr--, to--;
addEdge(fr, to, 1, w);
addEdge(to, fr, 1, w);
}
printf("%dn", minCostFlow(s, t, 2));
}
return 0;
}