題目連結
題意:給出1~n點和m條無向邊,要求從1走到n再從n回到1處的最小費用,要求每條邊走過不超過1次
題解:可轉換為求從1到n的流量f=2的最小費用流問題(不可先從左到右掃一遍最短路再删去使用過的邊最後再次最短路回起點,隻做到局部最優而非全局)最小費用最大流(Dijkstra+最大流算法)O(F|E|log|V|)或O(F|V|^2)
代碼如下:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<functional>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = (int)2e5 + 50;
typedef pair<int, int>P; //first->最短路距離 second->頂點編号
struct edge {
int to, cap, cost, rev;
};
int V;//頂點數
vector<edge>G[maxn];
int h[maxn]; //頂點的勢,用來避免負環的出現
int dist[maxn];//最短距離
int prevv[maxn], preve[maxn];//最短路的前驅結點和對應的邊
void add(int from, int to, int cap, int cost) {
edge ee;
ee.to = to, ee.cap = cap, ee.rev = G[to].size(), ee.cost = cost;
G[from].push_back(ee);
ee.to = from, ee.cap = 0, ee.rev = G[from].size() - 1, ee.cost = -cost;
G[to].push_back(ee);
}
int min_cost_flow(int s, int t, int f) {
int res = 0;
fill(h, h + V, 0);//初始化h
while (f > 0) {
//使用Dijkstra算法更新h
priority_queue<P, vector<P>, greater<P> >q; //greater需要<functional>頭檔案,注意> >中間要加" "
fill(dist, dist + V, inf);
dist[s] = 0;
q.push(P(0, s));
while (!q.empty()) {
P p = q.top(); q.pop();
int v = p.second;
if (dist[v] < p.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];
prevv[e.to] = v;
preve[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];
//沿s->t的最短路盡量增廣
int d = f;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
f -= d;
res += d*h[t];
for (int v = t; v != s; v = prevv[v]) {
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
int main() {
int m, u, v, w;
while (~scanf("%d%d", &V, &m)) {
while (m--) {
scanf("%d%d%d", &u, &v, &w);
u--, v--;
add(u, v, 1, w);
add(v, u, 1, w);
}
printf("%d\n", min_cost_flow(0, V - 1, 2));//這個是從0到v-1的
}
return 0;
}