UVA 10806 Dijkstra, Dijkstra. ——最小费最大流

UVA 10806 Dijkstra, Dijkstra. ——最小费最大流

这种题我应该做了3遍了。。。。。。拿以前的代码稍微一改切个水题

#include #include #include #include #include #include using namespace std;const int maxn = 1005;const int INF = 0x3f3f3f3f;typedef pair P;struct Edge { int to, cap, cost, rev; Edge(int a, int b, int c, int d) : to(a), cap(b), cost(c), rev(d) {}};int V;vector G[maxn];int h[maxn];int dist[maxn];int prevv[maxn], preve[maxn];void init() { for (int i = 0; i < maxn; i++) G[i].clear();}void addedge(int u, int v, int cap, int cost) { G[u].push_back(Edge(v, cap, cost, G[v].size())); G[v].push_back(Edge(u, 0, -cost, G[u].size()-1));}int min_cost_flow(int s, int t, int f) { int res = 0; memset(h, 0, sizeof(h)); while (f > 0) { priority_queue, greater

> q; memset(dist, INF, sizeof(dist)); dist[s] = 0; q.push(P(0, s)); while (!q.empty()) { P p = q-(); 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]; 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 n, m, u, v, cost; while (~scanf("%d", &n) && n) { scanf("%d", &m); init(); int s = 0, t = n - 1; V = n; while (m--) { scanf("%d %d %d", &u, &v, &cost); addedge(u-1, v-1, 1, cost); addedge(v-1, u-1, 1, cost); } int ans = min_cost_flow(s, t, 2); if (ans == -1) printf("Back to jail\n"); else printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。