题目意思是要从点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;
}