HDOJ 3677 - Transportation 构图拆边,最小费用最大流

HDOJ 3677 - Transportation 构图拆边,最小费用最大流

题目意思是要从点1运送K个货物到点N..每条边有最大容量以及单位费用...经过一条路的费用计算为a*x^2..a为改路单位费用..x为所带货物重量...问运送完K个物品最少所需的费用..

很明显的最小费用最大流...但不是裸的..因为a*x^2不是线性关系...直接跑模板会错..例如样例的第三组数据....那么为了能做最小费用最大流..就要想办法将flow与单位费用的关系转化为线性的...

由于对于任意正整数x有x^2=1+3+5+..(2*x-1)....

那么对于a*x^2可以等价为a*(1*x+3*x+5*x+... (2*x-1)*x) = (1*a+3*a+5*a+...(2*x-1)*a)*x=1*(a*x)+3*(a*x)+5*(a*x)+..(2*x-1)*(a*x)..

而a*x是线性关系了....并且数据范围给出每个点的C最多为5也就是说拆边最多拆成5条边...所以可以拆...

比如说有条边为(s=1,e=2,a=2,c=4)将其拆成4个边:   (s=1,e=2,a=2*1,c=1) (s=1,e=2,a=2*3,c=1)(s=1,e=2,a=2*5c=1)(s=1,e=2,a=2*7,c=1)

Program:

#include#include#include#include#include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)using namespace std;struct node{ int x,y,c,a,next; }line[100005];int N,M,K,flow,cost,_next[125],pre[125],dis[125]; queue myqueue;bool inqueue[125];void addline(int x,int y,int num,int a,int c){ line[num].next=_next[x],_next[x]=num; line[num].x=x,line[num].y=y,line[num].a=a,line[num].c=c; return;}bool SPFA(){ int x,k; while (!myqueue.empty()) myqueue.pop(); memset(pre,0,sizeof(pre)); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); myqueue.push(1); dis[1]=0; while (!myqueue.empty()) { x=myqueue.front(); myqueue.pop(); inqueue[x]=false; k=_next[x]; while (k) { if (line[k].c && dis[line[k].y]>dis[x]+line[k].a) { dis[line[k].y]=dis[x]+line[k].a; pre[line[k].y]=k; if (!inqueue[line[k].y]) { inqueue[line[k].y]=true; myqueue.push(line[k].y); } } k=line[k].next; } } if (dis[N]>oo) return false; cost=dis[N],flow=oo; x=pre[N]; while (x) { flow=min(flow,line[x].c); x=pre[line[x].x]; } x=pre[N]; while (x) { line[x].c-=flow; if (x%2) line[x+1].c+=flow; else line[x-1].c+=flow; x=pre[line[x].x]; } return true; }int MinCost_MaxFlow(){ int i,MaxFlow=0,MinCost=0; while (MaxFlow

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