HDU 3667 Transportation(最小费用最大流)
http://acm.hdu.edu.cn/showproblem.php?pid=3667
题意:
有N个节点M条边的有向图,现在你需要从1号节点运送k个货物到N号节点. 每条边都有一个ai和ci值,ci值是指该边最多能运ci个货物,而你如果在该边运x(1<=x<=ci)个货物需要花费ai*x*x代价.问你运送这k个货物的最小代价是多少?
分析:
其实该题就是普通的最小费用最大流问题,现在如下建图:
源点s编号0, n个节点编号1到n, 其中汇点t编号n.
从源点s到1号节点有边 (s, 1, k, 0)
如果i点和j点间有c容量a系数的边,那么就建边(i, j, 1, a) ,(i,j,1,a*3),…(i,j,1,a*(2*c-1)).(就是把一条边分成多条,如果c==3,那么就分成容量都为1,但是费用为a,3a,5a的三条边,这样最小费用流肯定优先走费用低的边,当该边满流时,最小费用流的费用正好==a*3*3.)
最终如果最大流==K,那么输出最小费用,否则输出-1.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn=100+5;
struct Edge
{
int from,to,cap,flow,cost;
Edge(){}
Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
};
struct MCMF
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int a[maxn];
int p[maxn];
void init(int n,int s,int t)
{
this->n=n, this->s=s, this->t=t;
edges.clear();
for(int i=0;i<n;++i) G[i].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 BellmanFord(int &flow,int &cost)
{
queue<int> Q;
for(int i=0;i<n;++i) d[i]=INF;
memset(inq,0,sizeof(inq));
d[s]=0,a[s]=INF,p[s]=0,inq[s]=true,Q.push(s);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
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;
a[e.to] = min(a[u],e.cap-e.flow);
p[e.to] = G[u][i];
if(!inq[e.to]) {inq[e.to]=true; Q.push(e.to);}
}
}
}
if(d[t]==INF) return false;
flow += a[t];
cost += d[t]*a[t];
int u=t;
while(u!=s)
{
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -=a[t];
u = edges[p[u]].from;
}
return true;
}
int solve(int k)
{
int flow=0,cost=0;
while(BellmanFord(flow,cost));
return flow==k? cost:-1;
}
}MM;
int main()
{
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k)==3)
{
int src=0,dst=n;
MM.init(n+1,src,dst);
MM.AddEdge(src,1,k,0);
while(m--)
{
int u,v,a,c;
scanf("%d%d%d%d",&u,&v,&a,&c);
for(int i=1;i<=c;++i)
MM.AddEdge(u,v,1,a*(2*i-1));
}
printf("%d\n",MM.solve(k));
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
B_(HDU_1231)(最大子段和,分治).cpp
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
Least Common Multiple ...先利用gcd算法求两个数的最大公约数,再考虑最小公倍数=两数乘积/最大公约数,即可求得最小公倍数。 注意:要考虑到输入的输入的n个数中的0,有0的要去掉0求其他数的最小公倍数。 代码:
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类