# UVA10806 Dijkstra, Dijkstra. （无向图最小费用最大流/最短路）

## Dijkstra, Dijkstra.

You are a political prisoner in jail. Things are looking grim, but fortunately, your jailmate has come up with an escape plan. He has found a way for both of you to get out of the cell and run through the city to the train station, where you will leave the country. Your friend will escape first and run along the streets of the city to the train station. He will then call you from there on your cellphone (which somebody smuggled in to you inside a cake), and you will start to run to the same train station. When you meet your friend there, you will both board a train and be on your way to freedom.
Your friend will be running along the streets during the day, wearing his jail clothes, so people will notice. This is why you can not follow any of the same streets that your friend follows - the authorities may be waiting for you there. You have to pick a completely different path (although you may run across the same intersections as your friend).
What is the earliest time at which you and your friend can board a train?

### Problem, in short

Given a weighed, undirected graph, find the shortest path from S to T and back without using the same edge twice.

### Input

The input will contain several test cases. Each test case will begin with an integer n (2 ≤ n ≤ 100) — the number of nodes (intersections). The jail is at node number 1, and the train station is at node number n. The next line will contain an integer m — the number of streets. The next m lines will describe the m streets. Each line will contain 3 integers — the two nodes connected by the street and the time it takes to run the length of the street (in seconds). No street will be longer than 1000 or shorter than 1. Each street will connect two different nodes. No pair of nodes will be directly connected by more than one street. The last test case will be followed by a line containing zero.

### Output

For each test case, output a single integer on a line by itself — the number of seconds you and your friend need between the time he leaves the jail cell and the time both of you board the train. (Assume that you do not need to wait for the train — they leave every second.) If there is no solution, print ‘Back to jail’.

### Sample Input

2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50
9
12
1 2 10
1 3 10
1 4 10
2 5 10
3 5 10
4 5 10
5 7 10
6 7 10
7 8 10
6 9 10
7 9 10
8 9 10
0

### Sample Output

Back to jail
80
Back to jail

### 链接

https://cn.vjudge.net/problem/UVA-10806

### 题解

• bin神，昨天问的那个题还是没太明白，就是无向图最小费用最大流转化为两条有向边的时候不会走两条，它的相互抵消指的是什么呢？两条有向边的容量都为正呀。
麻烦bin神有时间的时候解答下，谢啦
• 是的，容量都为正，费用流可以理解成一条河流，两个点之间只会有单向的存在。如果他们费用都是正的，那么应该互相抵消

### 代码

StatusAccepted
Length2754
• 最小费用最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 110; // 点数
const int maxm = 10010; // 边数
const int inf = 0x3f3f3f3f;

struct Edge
{
int to, next, cap, flow, cost;
}edge[maxm<<2];

int n, m, tot;
bool vis[maxn];

void init()
{
tot = 0;
}

void addedge(int u, int v, int cap, int cost) // 链式前向星存图
{
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = 0;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].cost = -cost;
edge[tot].flow = 0;
}

bool spfa(int s, int t) // spfa寻找最小费用增广路
{
queue <int> Q;
for (int i = 0; i <= n + 1; ++i)
{
dis[i] = inf;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if (!vis[v])
{
vis[v] = true;
Q.push(v);
}
}
}
}
if (pre[t] == -1)
return false;
return true;
}

int minCostMaxflow(int s, int t, int &mincost) // 计算费用
{
int maxflow = 0;
mincost = 0;
while (spfa(s, t))
{
int Min = inf;
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) // 每次增加的流量
Min = min(Min, edge[i].cap - edge[i].flow);
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
mincost += edge[i].cost * Min;
}
maxflow += Min;
}
return maxflow;
}

int main()
{
int u, v, cost, cap, s, t;
while (scanf("%d", &n) != EOF)
{
if (n == 0)
break;
scanf("%d", &m);
init();
s = 0, t = n + 1, cap = 1;
for (int i = 1; i <= m; ++i) // 无向边转化为两条有向边
{
scanf("%d%d%d", &u, &v, &cost);
}
addedge(s, 1, 2, 0); // 超级源和起点，容量为2，费用为0
addedge(n, t, 2, 0); // 终点和超级汇，容量为2，费用为0
int maxflow, mincost = 0;
maxflow = minCostMaxflow(s, t, mincost);
if (maxflow != 2) // 最大流不为2，失败
printf("Back to jail\n");
else
printf("%d\n", mincost);
}
return 0;
}
• 两遍spfa

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int g[N][N];
int d[N];
int p[N];
int vis[N];
int n, m;
int s, t;
int spfa(int s, int t) {
queue<int> q;
memset(vis , 0 ,sizeof(vis));
for(int i = 1; i <= n; i++)
d[i] = (i == s) ? 0 : INF;
q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int v = 1; v <= n; v++) if(g[u][v]){
if(d[v] > d[u] + g[u][v]) {
d[v] = d[u] + g[u][v];
p[v] = u;
if(!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return d[t];
}
void change(int u) {
if(p[u] == -1)
return ;
g[u][p[u]] = -g[u][p[u]];
g[p[u]][u] = INF;
change(p[u]);
}
int main(){
while(scanf("%d",&n) && n) {
memset(g, INF, sizeof(g));
memset(p, -1, sizeof(p));
scanf("%d", &m);
while(m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = c;
}
int ans = spfa(1, n);
change(n);
ans += spfa(1, n);
if(ans < INF)
printf("%d\n", ans);
else
printf("Back to jail\n");
}
return 0;
}

The end.
2018-08-21 星期二