本文主要是介绍hdu 3667 Transportation（最小费用最大流+拆边），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
求从城市1运送K单位物品到城市n的最小花费。给定的有向边，每条边都有其容量c，并且，产生的费用是 a * ( f * f )，其中f是这条边上的流量，a是给出的系数。
思路：
这个题目就是刘汝佳训练指南上建模与建图的一种，费用与流量的平方成正比的最小流。容量c均为整数，并且每条弧还有一个费用系数a，表示该弧流量为x时费用为a*x*x,如何求最小费用最大流?
用拆边法，如图
图更正： 最后一个cost=9a，（图有点丑）
一个费用系数为a，容量为5的边被拆成5条容量为1费用各异的弧，因为求的是最小费用流，如果这条弧的流量为1，走的肯定是cost=1的那条弧；如果流量为2，肯定走的是cost=1和cost=3的那两条；如果流量为3，走的肯定是 cost=1,3,5那三条。。。。。。不难验证，不管流量是1~5中间的哪一个，左右两个图都是等价的。这样就转化为普通的最小费用最大流问题。需要注意的是，因为有重边，普通的邻接矩阵无法满足要求。要么采用模板 最小费用最大流（刘汝佳 p363），要么采用把邻接矩阵加一维，表示某两点间的第几条弧。
此题分析：给定一条边(u,v)，其计费系数为a，容量为c，那么可以把(u,v)拆成5条边，费用为(1a,3a,5a,7a,9a)，容量都为1，。对所有输入的有向边，按照上述方法拆边建图，然后加入超级源点s(0)，s连向1，容量为K，费用为0。然后跑一遍最小费用最大流，若流量不等于K，则输出-1，否则输出最小费用。
代码：
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std; #define end() return 0 typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull; const int maxn = 100 + 5;
const int INF = 0x7f7f7f7f; struct Edge{ int from,to,cap,flow,cost; Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
}; struct MCMF{ int n,m,flow,cost; vector<Edge>edge; //边数的两倍 vector<int>G[maxn]; //邻接表，G[i][j]表示i的第j条边在e数组中的序号 int inq[maxn]; //是否在队列 int d[maxn]; //Bellman-Ford int p[maxn]; //上一条弧 int a[maxn]; //可改进量 void init(int n){ this -> n = n; for(int i=0;i<=n;i++) G[i].clear(); edge.clear(); } void addEdge(int from,int to,int cap,int cost){ edge.push_back(Edge(from,to,cap,0,cost)); edge.push_back(Edge(to,from,0,0,-cost)); m=edge.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s,int t,int& flow,int& cost){ memset(d,INF,sizeof(d)); 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=edge[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 false; flow+=a[t]; cost+=d[t]*a[t]; for(int u=t;u!=s;u=edge[p[u]].from){ edge[p[u]].flow+=a[t]; edge[p[u]^1].flow-=a[t]; } return true; } //需要保证初始网络中没有负权圈 void MincostMaxflow(int s,int t){ flow=0,cost=0; while(BellmanFord(s,t,flow,cost)); }
}; struct EDGE{ int u,v,a,c; EDGE(){} EDGE(int u,int v,int a,int c):u(u),v(v),a(a),c(c){}
}; int N,M,K;
int u,v,a,c;
EDGE edges[5005];
MCMF mcmf; void input(){ for(int i=1;i<=M;i++){ scanf("%d%d%d%d",&u,&v,&a,&c); edges[i]=EDGE(u,v,a,c); }
} void createGraph(){ mcmf.init(N+1); mcmf.addEdge(0,1,K,0); for(int k=1;k<=M;k++){ int x=edges[k].c*edges[k].c; for(int i=1,j=1;j<=x;i+=2,j+=i){ mcmf.addEdge(edges[k].u,edges[k].v,1,edges[k].a*i); } }
} void solve(){ createGraph(); mcmf.MincostMaxflow(0,N); if(mcmf.flow==K) printf("%d\n",mcmf.cost); else printf("-1\n");
} int main(){ while(scanf("%d%d%d",&N,&M,&K)!=EOF){ input(); solve(); }return 0;
}
这篇关于hdu 3667 Transportation（最小费用最大流+拆边）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
