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<iostream>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stdio.h>
#include<stack>
#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<int> 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<K && SPFA())
       {
             MaxFlow+=flow;
             MinCost+=cost*flow;
       }       
       if (MaxFlow<K) return -1;
       return MinCost;
}
int main()
{
       int x,y,a,c,num,i;
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
       while (~scanf("%d%d%d",&N,&M,&K))
       {
               memset(_next,0,sizeof(_next));
               num=0;
               while (M--)
               {
                     scanf("%d%d%d%d",&x,&y,&a,&c);
                     for (i=1;i<=c;i++) addline(x,y,++num,a*(i*2-1),1),addline(y,x,++num,a*(1-i*2),0);
               }
               printf("%d\n",MinCost_MaxFlow());
       }
       return 0;
}