首页 > 代码库 > AHU-835 FJ的旅行 【最小费用最大流】
AHU-835 FJ的旅行 【最小费用最大流】
Description
每当西瓜的朋友来西瓜家看他,西瓜总是喜欢带他们逛自己的豪宅。西瓜的豪宅有N幢楼(1<=N<=1000),用1到N的整数编号。1号楼是西瓜豪宅的大门,N号楼是西瓜的储藏室。西瓜的豪宅里总共有M条道路(1<=M<=10000)。每条道路连接两栋不同的楼房,道路的长度不超过35000。
为了最好地炫耀他的豪宅,西瓜准备从大门出发,经过一些楼房到达储藏室,再经过一些楼房回到自己的大门。
他要求他的路径越短越好,但是不能经过任意一条道路多于一次。请你计算这样的一条最短路径。西瓜保证这样的路径是存在的。
Input
第一行:N和M
第2..M+1行:每行三个整数表示一条道路(起点,终点,长度)
Output
一个整数,表示最短路径长度
Sample Input
4 5 1 2 1 2 3 1 3 4 1 1 3 2 2 4 2
Sample Output
6
题解:
一开始当成最短路做,发现有很多bug根本不能做,学了费用流发现可以做,设一个源点到1的费用为0容量为2,设一个汇点,从n到汇点的费用为0容量为2,其他弧费用为路径长度,容量为1,跑最小费用最大流算法可以过。
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 0x3f3f3f3f 4 #define M(a, b) memset(a, b, sizeof(a)) 5 const int N = 1100; 6 struct Edge { 7 int from, to, cap, flow, cost; 8 }; 9 10 struct MCMF { 11 int n, m; 12 vector<Edge> edges; 13 vector<int> G[N]; 14 int d[N], inq[N], p[N], a[N]; 15 16 void init(int n) { 17 this->n = n; 18 for (int i = 0; i <= n+1; ++i) G[i].clear(); 19 edges.clear(); 20 } 21 22 void AddEdge(int from, int to, int cap, int cost) { 23 edges.push_back((Edge){from, to, cap, 0, cost}); 24 edges.push_back((Edge){to, from, 0, 0, -cost}); 25 m = edges.size(); 26 G[from].push_back(m-2); G[to].push_back(m-1); 27 } 28 29 bool spfa(int s, int t, int &flow, int &cost) { 30 M(inq, 0); M(d, INF); 31 d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 32 queue<int> q; 33 q.push(s); 34 while (!q.empty()) { 35 int x = q.front(); q.pop(); 36 inq[x] = 0; 37 for (int i = 0; i < G[x].size(); ++i) { 38 Edge &e = edges[G[x][i]]; 39 if (d[e.to] > d[x] + e.cost && e.cap > e.flow) { 40 d[e.to] = d[x] + e.cost; 41 p[e.to] = G[x][i]; 42 a[e.to] = min(a[x], e.cap-e.flow); 43 if (inq[e.to]) continue; 44 q.push(e.to); inq[e.to] = 1; 45 } 46 } 47 } 48 if (d[t] == INF) return false; 49 flow += a[t]; 50 cost += d[t] * a[t]; 51 int u = t; 52 while (u != s) { 53 edges[p[u]].flow += a[t]; 54 edges[p[u]^1].flow -= a[t]; 55 u = edges[p[u]].from; 56 } 57 return true; 58 } 59 60 int Mincost(int s, int t) { 61 int flow = 0, cost = 0; 62 while (spfa(s, t, flow, cost)); 63 return cost; 64 } 65 66 }solver; 67 68 int main() { 69 int n, m; 70 while (~scanf("%d%d", &n, &m)) { 71 solver.init(n); 72 solver.AddEdge(0, 1, 2, 0); 73 solver.AddEdge(n, n+1, 2, 0); 74 int from, to, cost; 75 for (int i = 0; i < m; ++i) { 76 scanf("%d%d%d", &from, &to, &cost); 77 solver.AddEdge(from, to, 1, cost); 78 solver.AddEdge(to, from, 1, cost); 79 } 80 printf("%d\n", solver.Mincost(0, n+1)); 81 } 82 83 return 0; 84 }
AHU-835 FJ的旅行 【最小费用最大流】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。