本文主要是介绍【POJ - 2135 】【最小费用最大流】【裸】【1-n-1不重复路的最小值】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2135
【题意】
求1->n->1不重复路的最短路
【题解】最小费用最大流的模板题
最小费用最大流-->多次s'p'fa-->满足最大情况下，用spfa找可行流的最短路径
建图：源点s:0,汇点t:n+1
1.add(s,1,2(流量),0（费用）)
2.add(n,t,2,0)
3.add(u,v,1,0)
add(v,u,1,0)
【代码】
#include<iostream>
#include <algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int INF = 100000000;
const int N = 1005;
struct edge
{int from, to, cap, flow, cost;edge(int u, int v, int c, int f, int co) :from(u), to(v), cap(c), flow(f), cost(co) {}
};
struct MCMF
{int n, m;vector<edge>edges;vector<int>g[N];int inq[N];int d[N];int p[N];int a[N];void init(int n) {this->n = n;for (int i = 0; i <= n; i++)g[i].clear();edges.clear();}void addedge(int from, int to, int cap, int cost) {edges.push_back(edge(from, to, cap, 0, cost));edges.push_back(edge(to, from, 0, 0, -cost));m = edges.size();g[from].push_back(m - 2);g[to].push_back(m - 1);}bool spfa(int s, int t, int &flow, int &cost) {for (int i = 0; i <= n; i++)d[i] = INF;memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;queue<int>q;q.push(s);while (!q.empty()) {int u = q.front(); q.pop();inq[u] = 0;for (int i = 0; i<g[u].size(); i++) {edge &e = edges[g[u][i]];if (e.cap>e.flow&&d[e.to]>d[u] + e.cost) {d[e.to] = d[u] + e.cost;p[e.to] = g[u][i];a[e.to] = min(a[u], e.cap - e.flow);if (!inq[e.to]) { q.push(e.to); inq[e.to] = 1; }}}}if (d[t] == INF)return 0;flow += a[t];cost += d[t] * a[t];for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}return 1;}int MincoatMaxflow(int s, int t, int& cost) {int flow = 0; cost = 0;while (spfa(s, t, flow, cost));return flow;}
};
int main()
{int m, n;MCMF mcmf;scanf("%d%d", &n, &m);mcmf.init(n + 1);while (m--) {int u, v, w;scanf("%d%d%d", &u, &v, &w);mcmf.addedge(u, v, 1, w);mcmf.addedge(v, u, 1, w);}mcmf.addedge(0, 1, 2, 0);mcmf.addedge(n, n + 1, 2, 0);n++;int cost = 0;int ans = mcmf.MincoatMaxflow(0, n, cost);cout << cost << endl;
}
这篇关于【POJ - 2135 】【最小费用最大流】【裸】【1-n-1不重复路的最小值】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
