学步园

刚开始没想着拆边，写完了连实例都过不了，仔细想了一下，如过直接做的话，会选择一条路，增加的流量是最小边的满流，而不去其余的路，这样就不对了，费用是跟流量的平方相关的。每条边的流量最大是五，拆成五条边还是可以的，，不过拆边后每条边的费用怎么算困扰我一天多，如果拆的几条边分别对应第几次走的话，第一次就是a*1*1，如果该路上流量为2的话，总费用就是a*2*2，所以第二次走费用就是a*2*2-a*1*1=a*3,之后就是a*5，a*7,a*9;

#include<stdio.h>
#include<queue>
#include<string.h>
const int N=110;
const int inf=0x3fffffff;
using namespace std;
int pp[6]={0,1,3,5,7,9};
int dist[N],head[N],num,n,start,end,vis[N],pre[N],k;
struct edge
{
	int st,ed,cost,flow,next;
}e[N*1000];
void addedge(int x,int y,int c,int w)
{
	e[num].st=x;e[num].ed=y;e[num].cost=c; e[num].flow=w;e[num].next=head[x];head[x]=num++;
	e[num].st=y;e[num].ed=x;e[num].cost=-c;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
int SPFA()
{
	int i,v,u;
	queue<int>Q;
	for(i=start;i<=end;i++)
	{dist[i]=inf;vis[i]=0;pre[i]=-1;}
	dist[start]=0;vis[start]=1;
	Q.push(start);
	while(!Q.empty())
	{
		u=Q.front();Q.pop();
		vis[u]=0;
		for(i=head[u];i!=-1;i=e[i].next)
		{
			v=e[i].ed;
			if(e[i].flow>0&&dist[v]>dist[u]+e[i].cost)
			{
				pre[v]=i;dist[v]=dist[u]+e[i].cost;
				if(vis[v]==0)
				{
					vis[v]=1;
					Q.push(v);
				}
			}
		}
	}
	if(pre[end]==-1)
		return 0;
	return 1;
}
int Mincost()
{
	int minflow,maxflow=0,mincost=0,i;
	while(SPFA())
	{
		minflow=inf;
		for(i=pre[end];i!=-1;i=pre[e[i].st])
		  if(minflow>e[i].flow)
			  minflow=e[i].flow;
		  maxflow+=minflow;
		  for(i=pre[end];i!=-1;i=pre[e[i].st])
		  {
			  e[i].flow-=minflow;
			  e[i^1].flow+=minflow;
			  mincost+=e[i].cost*minflow*minflow;
		  }
	}
	if(maxflow==k)
		return mincost;
	else return -1;

}
int main()
{
	int i,j,x,y,c,w,m;
	while(scanf("%d%d%d",&n,&m,&k)!=-1)
	{
		memset(head,-1,sizeof(head));
		num=0;start=0;end=n+1;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d%d",&x,&y,&c,&w);
			for(j=1;j<=w;j++)
			addedge(x,y,pp[j]*c,1);
		}
		addedge(start,1,0,k);
		addedge(n,end,0,k);
		printf("%d\n",Mincost());
	}
	return 0;
}