bzoj1877: [SDOI2009]晨跑（最小费用最大流+模板）

题目超链接

过渡型良心题，构图简单，流量简单，就是要教会你费用流是什么！

题目大意：

1、n个点，m条单向边；每条边有费用（通过的时间），每条边只能走一次（流量限制）；

2、求用走的边尽可能多，并且时间尽可能短。（最小费用+最大流）

解题思路：

1、请结合最大流的模板对比学习，会更加容易搞到懂；

2、这题因为每条边的流量为 1，所以，是个良心的过渡型模板题，但是费用流和最大流在实现上有一个函数的区别：

    1）最大流：是用 bfs 将点分层，然后 跑 dfs 推流量；

    2）费用流：还是用 bfs 分层，但是（按最小费用）来分层，其实就是跑 spfa（spfa不懂的朋友，下次咱们再复习）；

    3）每次 spfa 的过程，用 a[x].f 记录来路；跑完一次完整的spfa之后，可以算出（当前这次流量）的最小费用；

    4）根据 a[x].f 的记录，用循环往回跑，找出这次用过的边，做一下流量反向。

    5）其实基础思维和最大流差不多，只是分层的机制改成了费用，并且将 dfs 函数 省掉（感觉会慢一点点，猜的）

3、构图也比较简单，因为每个点只能跑一次，直接拆点就可以了。

上代码：

（这次我把点的邻接表last参数单独拆出来作为la[ ]数组，多点尝试不同的习惯）

#include<cstdio>
#include<cstring>
const int mx=1000,inf=999999999;

int n,m,len=0,st,ed;
int la[mx];//邻接表的last参数 
int tou,wei,l[mx];//队列用
 
struct nodx{int d,v,f;}a[mx];//f参数是记录 流量的来路 
struct nodb{int x,y,c,d,f,gg;}b[mx*mx];

void ins(int x,int y,int c,int d)//反向边+费用d 
{
	len++;b[len].x=x;b[len].y=y;b[len].c=c;b[len].d=d;
	b[len].f=len+1;b[len].gg=la[x];la[x]=len;
	len++;b[len].x=y;b[len].y=x;b[len].c=0;b[len].d=-d;//回头要把消耗的费用还回来，所以是-d 
	b[len].f=len-1;b[len].gg=la[y];la[y]=len;
}

bool spfa()
{
	for(int i=1;i<=ed;i++) { a[i].v=0; a[i].d=inf; } 
	a[st].d=0;a[st].v=1;
	l[1]=st;tou=1;wei=2;
	while(tou!=wei)
	{
		int x=l[tou];
		for(int i=la[x];i>0;i=b[i].gg)
		{
			int y=b[i].y;
			if(a[y].d>a[x].d+b[i].d&&b[i].c>0) //费用更大的，更新
			{
				a[y].d=a[x].d+b[i].d;
				a[y].f=i;//记录来时的路 
				if(a[y].v==0)
				{
					a[y].v=1;l[wei++]=y;if(wei>ed) wei=1;
				}
			} 
		}
		a[x].v=0; tou++; if(tou>ed) tou=1;
	}
	int x=ed;
	while(x!=st) //找到最短路（最小费用的路）之后，封路 
	{
		int i=a[x].f;
		b[i].c-=1; b[b[i].f].c+=1;  
		x=b[i].x;
	}
	if(a[ed].d==inf) return 0; return 1;
}

int main()
{
	scanf("%d %d",&n,&m); memset(la,0,sizeof(la));
	st=1,ed=n*2;
	
	ins(1,n+1,inf,0);//拆源点 
	ins(n,n*2,inf,0);//拆汇点 
	for(int i=2;i<n;i++) ins(i,i+n,1,0);//拆点 
	
	for(int i=1;i<=m;i++)//从 xb->ya 
	{
		int x,y,c; scanf("%d %d %d",&x,&y,&c);
		ins(x+n,y,1,c);
	}
	int ans=0,su=0;//ans 记录流量，su记录费用 
	while(spfa())
	{
		ans++;//每次成功跑到终点，其实只跑了一个流量 
		su+=a[ed].d;//每次跑到终点产生的费用 
	}
	printf("%d %d\n",ans,su);
	return 0;
}