题意：有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。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #define min(x,y) (x)<(y)?(x):(y) 4 const int N=111,M=55555,INF=0x3f3f3f3f; 5 int pre[N],head[N],q[M],d[N],p[N]; 6 int s,t,cnt,l,r,k; 7 struct node 8 { 9 int u,v,c,w,next; 10 }e[M]; 11 void init() 12 { 13 memset(head,-1,sizeof(head)); 14 cnt=0; 15 } 16 void add(int u,int v,int c,int w) 17 { 18 e[cnt].u=u,e[cnt].v=v,e[cnt].c=c,e[cnt].w=w; 19 e[cnt].next=head[u],head[u]=cnt++; 20 e[cnt].u=v,e[cnt].v=u,e[cnt].c=0,e[cnt].w=-w; 21 e[cnt].next=head[v],head[v]=cnt++; 22 return ; 23 } 24 int spfa() 25 { 26 memset(d,0x3f,sizeof(d)); 27 memset(pre,-1,sizeof(pre)); 28 memset(p,0,sizeof(p)); 29 l=r=0;int u,v,i,c,w; 30 q[++r]=s;d[s]=0; 31 while(l<r) 32 { 33 p[u=q[++l]]=0; 34 for(i=head[u];i!=-1;i=e[i].next) 35 { 36 v=e[i].v,c=e[i].c,w=e[i].w; 37 if(c&&d[v]>d[u]+w) 38 { 39 d[v]=d[u]+w; 40 pre[v]=i; 41 if(!p[v]) 42 { 43 q[++r]=v; 44 p[v]=1; 45 } 46 } 47 } 48 } 49 if(pre[t]==-1) return 0; 50 return 1; 51 } 52 int MicMaf() 53 { 54 int ans=0,sum=0; 55 while(spfa()) 56 { 57 int v,f=INF; 58 for(v=t;v!=s;v=e[pre[v]].u) 59 f=min(f,e[pre[v]].c); 60 sum+=f; 61 ans+=f*d[t]; 62 for(v=t;v!=s;v=e[pre[v]].u) 63 { 64 e[pre[v]].c-=f; 65 e[pre[v]^1].c+=f; 66 67 } 68 } 69 if(sum!=k) return -1; 70 return ans; 71 } 72 int main() 73 { 74 int n,m,i,u,v,c,w; 75 while(scanf("%d%d%d",&n,&m,&k)!=EOF) 76 { 77 init(); 78 while(m--) 79 { 80 scanf("%d%d%d%d",&u,&v,&w,&c); 81 for(i=1;i<=c;i++) 82 add(u,v,1,w*(2*i-1)); 83 } 84 s=0,t=n+1; 85 add(s,1,k,0); 86 add(n,t,k,0); 87 printf("%d ",MicMaf()); 88 } 89 return 0; 90 }