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;
}