记录编号	153225	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2010] 网络扩容	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2015-03-17 15:02:32	内存使用	0.77 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define INF 1e9
int i,p,n,m,k,zj1,zj2,zj3,zj4,ST,SD,ans;
int zhi[10010]={0},sj=1;
int to[20010]={0},fr[20010]={0},ne[20010]={0},r[20010]={0},w[20010]={0},head[1010]={0};
inline void addedge(int u,int v,int z)
{
	to[++sj]=v,fr[sj]=u,ne[sj]=head[u],head[u]=sj,r[sj]=z;
	to[++sj]=u,fr[sj]=v,ne[sj]=head[v],head[v]=sj,r[sj]=0;
}
 
int que[1010]={0},qhead=1,qtail=0;bool flag[1010]={0};
inline int GET()
{int x=que[qhead];flag[x]=0,que[0]--;if(++qhead==1010)qhead=1;return x;}
inline void PUSH(int x)
{que[0]++,flag[x]=1;if(++qtail==1010)qtail=1;que[qtail]=x;}
 
int lv[1010]={0},cnt[1010]={0};
void init()
{
	scanf("%d%d%d",&n,&m,&k);
	while(m--)
	{
		scanf("%d%d%d%d",&zj1,&zj2,&zj3,&zj4);
		addedge(zj1,zj2,zj3);zhi[sj-1]=zj4;zhi[sj]=-zj4;
	}
	ST=1,SD=n;PUSH(SD);
	while(que[0])
	for(zj1=GET(),i=head[zj1];i;i=ne[i])
	if(!r[i]&&!lv[to[i]])
	cnt[lv[to[i]]=lv[zj1]+1]++,PUSH(to[i]);
	cnt[lv[SD]]--,cnt[lv[SD]=0]=SD;
}
int pre[1010],cur[1010]={0};
void isap()
{
	ans=0;
	for(i=1;i<=SD;i++)cur[i]=head[i];
	int U=ST;pre[ST]=ST,zj1=INF;bool FLAG;
	while(lv[ST]<SD)
	{
		for(FLAG=0,i=cur[U];i;i=ne[i])
		{
			if(r[i]&&lv[to[i]]==lv[U]-1)
			{
				FLAG=1,pre[to[i]]=U,U=to[i];
				if(r[i]<zj1)zj1=r[i];
				if(U==SD)
				{
					while(U!=ST)
					U=pre[U],r[cur[U]]-=zj1,r[cur[U]^1]+=zj1;
					ans+=zj1,zj1=INF;
				}
				break;
			}
			cur[U]=ne[i];
		}
		if(FLAG)continue;
		if(!(--cnt[lv[U]]))break;
		for(zj2=SD+1,i=head[U];i;i=ne[i])
		if(r[i]&&zj2>lv[to[i]])zj2=lv[to[i]],cur[U]=i;
		cnt[lv[U]=zj2+1]++,U=pre[U];
	}
	printf("%d ",ans);
}
 
void Make()
{
	ans=0,zj1=sj,ST=n+1;
	for(i=2;i<=zj1;i+=2)
	{
		addedge(fr[i],to[i],k);
		w[sj-1]=zhi[i];w[sj]=zhi[i+1];
	}
	addedge(ST,1,k);
}
int dis[1010]={0},pres[1010]={0};
inline bool spfa()
{
	for(i=1;i<=SD;i++)dis[i]=INF;
	dis[ST]=0;PUSH(ST);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=ne[i])
		if(r[i]&&(dis[to[i]]>(zj2=dis[zj1]+w[i])))
		{
			dis[to[i]]=zj2,pre[to[i]]=zj1,pres[to[i]]=i;
			if(!flag[to[i]])PUSH(to[i]);
		}
	}
	if(dis[SD]==INF)return 0;
	return 1;
}
 
void work()
{
	for(zj2=INF,zj1=SD;zj1!=ST;zj1=pre[zj1])
	if(r[pres[zj1]]<zj2)zj2=r[pres[zj1]];
	for(zj1=SD;zj1!=ST;zj1=pre[zj1])
	r[pres[zj1]]-=zj2,r[pres[zj1]^1]+=zj2;
	ans+=dis[SD]*zj2;
}
 
int main()
{
	freopen("networkzj2010.in","r",stdin);
	freopen("networkzj2010.out","w",stdout);
	init();
	isap();
	Make();
	while(spfa())work();
	printf("%d\n",ans);
	return 0;
}