题目链接：
题意：无向图，从1到n来回的最短路，不走重复路。
分析：可以考虑为1到n的流量为2时的最小花费；
建图： 一个点到一个点的容量为1，费用为距离。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int maxn = 100 + 10, INF = 1000000000; 10 11 12 struct Edge 13 { 14 int from, to, cap, flow, cost; 15 }; 16 17 struct MCMF 18 { 19 int n, m; 20 vector edges; 21 vector G[maxn]; 22 bool inq[maxn]; // 是否在队列中 23 int d[maxn]; // Bellman-Ford 24 int p[maxn]; // 上一条弧 25 int a[maxn]; // 可改进量 26 27 void init(int n) 28 { 29 this->n = n; 30 for(int i = 0; i < n; i++) G[i].clear(); 31 edges.clear(); 32 } 33 34 void AddEdge(int from, int to, int cap, int cost) 35 { 36 edges.push_back((Edge) 37 { 38 from, to, cap, 0, cost 39 }); 40 edges.push_back((Edge) 41 { 42 to, from, 0, 0, -cost 43 }); 44 m = edges.size(); 45 G[from].push_back(m-2); 46 G[to].push_back(m-1); 47 } 48 49 bool BellmanFord(int s, int t, int &flow, long long& cost) 50 { 51 memset(inq,0,sizeof(inq)); 52 for(int i=0;i
Q; 60 Q.push(s); 61 while(!Q.empty()) 62 { 63 int u = Q.front(); 64 Q.pop(); 65 inq[u] = false; 66 for(int i = 0; i < G[u].size(); i++) 67 { 68 Edge& e = edges[G[u][i]]; 69 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) 70 { 71 d[e.to] = d[u] + e.cost; 72 p[e.to] = G[u][i]; 73 a[e.to] = min(a[u], e.cap - e.flow); 74 if(!inq[e.to]) 75 { 76 Q.push(e.to); 77 inq[e.to] = true; 78 } 79 } 80 } 81 } 82 if(d[t] == INF) return false; //s-t 不连通，失败退出 83 flow += a[t]; 84 cost += (long long)d[t] * (long long)a[t]; 85 int u = t; 86 while(u != s) 87 { 88 edges[p[u]].flow += a[t]; 89 edges[p[u]^1].flow -= a[t]; 90 u = edges[p[u]].from; 91 } 92 return true; 93 } 94 95 pair
Mincost(int s, int t) 96 { 97 long long cost = 0; 98 int flow = 0; 99 while(BellmanFord(s, t, flow, cost));100 return pair {cost,flow};101 }102 };103 104 MCMF solver;105 int n;106 107 108 int main()109 {110 while(true)111 {112 scanf("%d", &n);113 if(n == 0) break;114 solver.init(n + 1);115 int m, from, to, cost;116 scanf("%d", &m);117 for(int i = 0; i < m; i++)118 {119 scanf("%d%d%d", &from, &to, &cost);120 solver.AddEdge(from, to, 1, cost);121 solver.AddEdge(to, from, 1, cost);122 }123 solver.AddEdge(0, 1, 2, 0);124 125 pair ans = solver.Mincost(0, n);126 int flow = ans.second;127 128 if(flow != 2)129 puts("Back to jail");130 else131 printf("%lld\n", ans.first);132 }133 return 0;134 }