首页 > 代码库 > uva 10806 Dijkstra, Dijkstra. (最小费最大流)
uva 10806 Dijkstra, Dijkstra. (最小费最大流)
uva 10806 Dijkstra, Dijkstra.
题目大意:你和你的伙伴想要越狱。你的伙伴先去探路,等你的伙伴到火车站后,他会打电话给你(电话是藏在蛋糕里带进来的),然后你就能够跑去火车站了,那里有人接应你。可是。由于你的伙伴跑去火车站的时候穿的是囚服,所以,他经过的街道都被戒严了,你必须从其它街道跑过去。
假设你能够到达火车站,请输出你和你的伙伴在路上花费的最短时间,假设不能请“Back to jail”。
解题思路:最小费最大流。设置一个超级源点连向监狱(起点1), 容量为2(两个人),设置一个超级汇点,使火车站(终点n)连向他,容量为2(两个人)。其余街道皆为无向(即正向反向都要考虑)。且容量为1(每条街道仅仅能跑一次)。最后求最大流,若最大流为2则输出最小费,否则回监狱准备下次越狱吧。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 105;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int a[N], pre[N], d[N], inq[N];
struct Edge{
int from, to, cap, flow;
ll cos;
};
vector<Edge> edges;
vector<int> G[3 * N];
void init() {
for (int i = 0; i < 3 * N; i++) G[i].clear();
edges.clear();
}
void addEdge(int from, int to, int cap, int flow, ll cos) {
edges.push_back((Edge){from, to, cap, 0, cos});
edges.push_back((Edge){to, from, 0, 0, -cos});
int m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
void input() {
int from, to;
ll cost;
for (int i = 0; i < m; i++) {
scanf("%d %d %lld", &from, &to, &cost);
addEdge(from, to, 1, 0, cost);
addEdge(to, from, 1, 0, cost);
}
addEdge(0, 1, 2, 0, 0);
addEdge(n, n + 1, 2, 0, 0);
}
int BF(int s, int t, int& flow, ll& cost) {
queue<int> Q;
memset(inq, 0, sizeof(inq));
memset(a, 0, sizeof(a));
memset(pre, 0, sizeof(pre));
for (int i = 0; i <= 2 * n + 1; i++) d[i] = INF;
d[s] = 0;
a[s] = INF;
inq[s] = 1;
int flag = 1;
pre[s] = 0;
Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cos) {
d[e.to] = d[u] + e.cos;
a[e.to] = min(a[u], e.cap - e.flow);
pre[e.to] = G[u][i];
if (!inq[e.to]) {
inq[e.to] = 1;
Q.push(e.to);
}
}
}
flag = 0;
}
if (d[t] == INF) return 0;
flow += a[t];
cost += (ll)d[t] * (ll)a[t];
for (int u = t; u != s; u = edges[pre[u]].from) {
edges[pre[u]].flow += a[t];
edges[pre[u]^1].flow -= a[t];
}
return 1;
}
int MCMF(int s, int t, ll& cost) {
int flow = 0;
cost = 0;
while (BF(s, t, flow, cost));
return flow;
}
int main() {
while (scanf("%d", &n) != EOF) {
if (n == 0) break;
scanf("%d", &m);
s = 0, t = n + 1;
init();
input();
ll cost = 0;
int ans = MCMF(s, t, cost);
if (ans == 1) printf("Back to jail\n");
else printf("%lld\n", cost);
}
return 0;
}
uva 10806 Dijkstra, Dijkstra. (最小费最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。