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

40 阅读 0 评论 27 点赞

我是靠谱客的博主俭朴大白，最近开发中收集的这篇文章主要介绍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;
}