poj 3068 有流量限制的最小费用网络流

题意：

m条有向边连接了n个仓库，每条边都有一定费用。

将两种危险品从0运到n-1，除了起点和终点外，危险品不能放在一起，也不能走相同的路径。

求最小的费用是多少。

解析：

抽象出一个源点s一个汇点t，源点与0相连，费用为0，容量为2。

汇点与n - 1相连，费用为0，容量为2。

每条边之间也相连，费用为每条边的费用，容量为1。

建图完毕之后，求一条流量为2的最小费用流就行了。

代码：

#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;
//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]; //前驱节点 以及对于的边
void init()
{
for (int i = 0; i <= V; i++)
{
g[i].clear();
}
}
//向图中增加一条从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
FIN;
#endif // LOCAL
int n, m;
int ca = 1;
while (~scanf("%d%d", &n, &m))
{
if (!n && !m)
break;
int s = 0, t = n + 1;
V = t + 1;
init();
addEdge(s, 1, 2, 0);
addEdge(n, n + 1, 2, 0);
for (int i = 0; i < m; i++)
{
int fr, to, cost;
scanf("%d%d%d", &fr, &to, &cost);
fr++, to++;
addEdge(fr, to, 1, cost);
}
int ans = minCostFlow(s, t, 2);
printf("Instance #%d: ", ca++);
if (ans == -1)
puts("Not possible");
else
printf("%dn", ans);
}
return 0;
}

最后

以上就是背后小鸽子为你收集整理的poj 3068 有流量限制的最小费用网络流的全部内容，希望文章能够帮你解决poj 3068 有流量限制的最小费用网络流所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。