uva 10806 Dijkstra, Dijkstra.
题目大意：你和你的伙伴想要越狱。你的伙伴先去探路，等你的伙伴到火车站后，他会打电话给你（电话是藏在蛋糕里带进来的），然后你就能够跑去火车站了，那里有人接应你。
可是。由于你的伙伴跑去火车站的时候穿的是囚服，所以，他经过的街道都被戒严了，你必须从其它街道跑过去。
假设你能够到达火车站，请输出你和你的伙伴在路上花费的最短时间，假设不能请“Back to jail”。
解题思路：最小费最大流。设置一个超级源点连向监狱（起点1）， 容量为2（两个人），设置一个超级汇点，使火车站（终点n）连向他，容量为2（两个人）。其余街道皆为无向（即正向反向都要考虑）。且容量为1（每条街道仅仅能跑一次）。最后求最大流，若最大流为2则输出最小费，否则回监狱准备下次越狱吧。
#include#include #include #include #include #include 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 edges;vector 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 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;}