题意：有n个城市(1~n)，m条有向边；有k件货物要从1运到n，每条边最多能运c件货物，每条边有一个危险系数ai，经过这条路的费用需要ai*x2(x为货物的数量)，问所有货物安全到达的费用。
思路：c<=5，这里可以做文章；把每条边拆成c条边，容量都为1，费用为ai*(2*i-1)（第二个i是指拆边时的第几条边）。推导:x2-(x-1)2=2x-1。
代码：
#include<stdio.h>
#include<string.h>
#define min(x,y) (x)<(y)?(x):(y)
const int N=,M=,INF=0x3f3f3f3f;
int pre[N],head[N],q[M],d[N],p[N];
int s,t,cnt,l,r,k;
struct node
{
int u,v,c,w,next;
}e[M];
void init()
{
memset(head,-,sizeof(head));
cnt=;
}
void add(int u,int v,int c,int w)
{
e[cnt].u=u,e[cnt].v=v,e[cnt].c=c,e[cnt].w=w;
e[cnt].next=head[u],head[u]=cnt++;
e[cnt].u=v,e[cnt].v=u,e[cnt].c=,e[cnt].w=-w;
e[cnt].next=head[v],head[v]=cnt++;
return ;
}
int spfa()
{
memset(d,0x3f,sizeof(d));
memset(pre,-,sizeof(pre));
memset(p,,sizeof(p));
l=r=;int u,v,i,c,w;
q[++r]=s;d[s]=;
while(l<r)
{
p[u=q[++l]]=;
for(i=head[u];i!=-;i=e[i].next)
{
v=e[i].v,c=e[i].c,w=e[i].w;
if(c&&d[v]>d[u]+w)
{
d[v]=d[u]+w;
pre[v]=i;
if(!p[v])
{
q[++r]=v;
p[v]=;
}
}
}
}
if(pre[t]==-) return ;
return ;
}
int MicMaf()
{
int ans=,sum=;
while(spfa())
{
int v,f=INF;
for(v=t;v!=s;v=e[pre[v]].u)
f=min(f,e[pre[v]].c);
sum+=f;
ans+=f*d[t];
for(v=t;v!=s;v=e[pre[v]].u)
{
e[pre[v]].c-=f;
e[pre[v]^].c+=f; }
}
if(sum!=k) return -;
return ans;
}
int main()
{
int n,m,i,u,v,c,w;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
init();
while(m--)
{
scanf("%d%d%d%d",&u,&v,&w,&c);
for(i=;i<=c;i++)
add(u,v,,w*(*i-));
}
s=,t=n+;
add(s,,k,);
add(n,t,k,);
printf("%d\n",MicMaf());
}
return ;
}