//费用流 
#include<stdio.h>
#include<string.h>
const int MAX=5100;
const int INF=1000000000;
const int MOD=1000000;
struct EDGE
{
	int cap,cost,v,next;
}edge[MOD];
int head[MAX],E,q[MOD];
bool used[MAX];
int pre[MAX],cur[MAX],dis[MAX];
void add_edge(int s,int t,int cap,int cost)
{
	edge[E].cap=cap;//容量 
	edge[E].cost=cost;//费用 
	edge[E].next=head[s];
	edge[E].v=t;
	head[s]=E++;
}
int min(int a,int b){return (a==-1||b<a)?b:a;}
int SPFA(int s,int t,int n)
{//运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流
	int f=-1,r=0;
	int i,v;
	q[r]=s;
	for(i=0;i<n;i++)
		 dis[i]=INF;
 	dis[s]=0;
	pre[s]=s;
	cur[s]=-1;
	memset(used,false,sizeof(bool)*n);
	used[s]=true;
	while(f!=r)
	{
		f++;
		if(f>=MOD)f-=MOD;
		s=q[f];
		used[s]=false;
		for(i=head[s];i!=-1;i=edge[i].next)
		{
			v=edge[i].v;
			if(edge[i].cap>0&&dis[s]+edge[i].cost<dis[v])
			{//这里是核心  要得到容量允许范围的的最小费用 
				dis[v]=dis[s]+edge[i].cost;
				pre[v]=s;//并且记录父亲节点便于下方函数的容量的改变 
				cur[v]=i;
				if(!used[v])
				{
					used[v]=true;
					r++;
					if(r>=MOD)r-=MOD;//为了防止数据太多溢出 
					q[r]=v;
				}
			}
		}
	}
	return dis[t];
}
int MinCost(int s,int t,int n)
{
	int ans=0;
	int u,v,cap;
	int cost;
	while(1)
	{
		cost=SPFA(s,t,n);
		if(cost==INF)break;
		u=v=t;
		cap=-1;
		for(u=pre[u];v!=s;v=u,u=pre[u])
		{
			cap=min(cap,edge[cur[v]].cap);//和sap算法很像 
		}
		ans+=cost*cap;
		u=v=t;
		for(u=pre[u];v!=s;v=u,u=pre[u])
		{
			edge[cur[v]].cap-=cap;
			edge[cur[v]^1].cap+=cap;
		}
	}
	return ans;
}
int main()
{
	int s=;
	int t=;
	E=0;
	memset(head,-1,sizeof(int)*(t+1));
}