poj 2135 Farm Tour(最小费用流)

本文主要是介绍poj 2135 Farm Tour(最小费用流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

求往返不能经过同一条道路两次，参观路线最小的最小值.可以转话为边的流量为1，总流量为2的最小费用流

约束:

1<= N <= 1000

1<= M <= 10000

1<= ai, bi <= N

1 <= ci <= 35000

/************************************************ Author: fisty* Created Time: 2015-08-17 16:09:15* File Name   : poj2135.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{N = n;tol = 0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{edge[tol].to = v;edge[tol].cap = cap;edge[tol].cost = cost;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = 0;edge[tol].cost = -cost;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++;
}
bool spfa(int s,int t)
{queue<int>q;for(int i = 0;i < N;i++){dis[i] = INF;vis[i] = false;pre[i] = -1;}dis[s] = 0;vis[s] = true;q.push(s);while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = head[u]; i != -1;i = edge[i].next){int v = edge[i].to;if(edge[i].cap > edge[i].flow &&dis[v] > dis[u] + edge[i].cost ){dis[v] = dis[u] + edge[i].cost;pre[v] = i;if(!vis[v]){vis[v] = true;q.push(v);}}}}if(pre[t] == -1)return false;else return true;
}
//返回的是最大流， cost存的是最小费用
int minCostMaxflow(int s,int t)
{int flow = 0;int cost = 0;while(spfa(s,t)){int Min = INF;for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){if(Min > edge[i].cap - edge[i].flow)Min = edge[i].cap - edge[i].flow;}for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){edge[i].flow += Min;edge[i^1].flow -= Min;cost += edge[i].cost * Min;}flow += Min;}return cost;
}
int n, M;
int a[MAXM], b[MAXM], c[MAXM];
void solve(){int s = n, t = n + 1;init(n + 2);for(int i = 0;i < M; i++){addedge(a[i]-1, b[i]-1, 1, c[i]);addedge(b[i]-1, a[i]-1, 1, c[i]);}addedge(s, 0, 2, 0);addedge(n-1, t, 2, 0);printf("%d\n", minCostMaxflow(s, t));
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);while(~scanf("%d%d", &n, &M)){  for(int i = 0;i < M; i++){    scanf("%d%d%d", &a[i], &b[i], &c[i]);}solve();}return 0;
}

这篇关于poj 2135 Farm Tour(最小费用流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---