最小费用最大流

bool spfa(int s, int t)
{
	queue<int> q;
	for (int i = 0; i < N; i++) 
	{
		dis[i] = INF; 
		vis[i] = false;  
		pre[i] = -1; 
	}  
	dis[s] = 0; 
	vis[s] = true; 
	q.push(s);  
	while (!q.empty())
	{
		int u = q.front(); 
		q.pop(); 
		vis[u] = false;  
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;    
			if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
			{ 
				dis[v] = dis[u] + edge[i].cost;      
				pre[v] = i;    
				if (!vis[v])
				{
					vis[v] = true;    
					q.push(v);
				}
			}
		}
	}  
	if (pre[t] == -1)   
		return false; 
	else  
		return true;
}

int minCostMaxflow(int s, int t, int &cost) //返回的是⼤大流,cost 存的是⼩小费⽤用 
{ 
	int flow = 0;  
	cost = 0;  
	while (spfa(s, t))
	{    
		int Min = INF;  
		for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) 
		{  
			if (Min > edge[i].cap - edge[i].flow) 
				Min = edge[i].cap - edge[i].flow;  
		}   
		for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
		{       
			edge[i].flow += Min;    
			edge[i ^ 1].flow -= Min;   
			cost += edge[i].cost * Min; 
		}  
		flow += Min; 
	} 
	return flow; 
} 

留下评论