本文共 2323 字，大约阅读时间需要 7 分钟。

题目链接

传送门：

题目大意

奥运会要开n天，这n天每天分别至少需要A_i个志愿者。现总共有M类志愿者，其中第i类可以从第S_i天工作到第T_i天，招募每人所需的费用是C_i元。求总费用最小是多少。

思路

我们把这n天的每一天看作一条边，流量就是志愿者，每天的边都有个流量下界即每天所需的最少人数。然后现在要满足第S_i天到第T_i天这些人的流动，我们从T_i+1点向S_i点连一条容量为正无穷，费用为C_i的边，就满足了这一类志愿者在S_i到T_i天间流动，并且还满足了流量守恒，如下图：

然后我们看代表天的这些边的下界分别是A_i（最少需要的人数），上界是正无穷（人数可以无限多）。所以我们就要按照处理的方法来求一个可行流：我们给每条边都减去他的下界，然后为了使流量守恒，我们要判断上一条边减去的下界（A_i-1）和该边减去的下界（A_i）的大小，我们将A_i-1记作last，A_i记作cur，如果last > cur，就从s向i连一条容量为last - cur，费用为0的边；如果last < cur，就从i向t连一条容量为cur - last，费用为0的边。这样子所得的新图G’的满流就是原图G的一个可行流，因为所有有费用的边只有T_i+1到S_i的边（红边），且这些边和原图的边都相同（因为流量下界是0，相当于没减），所以新图G’的费用和原图G的费用一样，所以在新图上求个最小费用最大流就是问题的解。

这道题的建图比较巧妙，将每一天并没有建成一个点，而是一条边，从而实现题目的限制。并且人员的流动是用一个圈来实现的，不仅能满足题意，而且能使流量守恒，从而建成一个流网络。然后此题将费用流与无源汇上下界可行流结合在一起，求无源汇上下界最小费用可行流，难想。

代码详解

#include
   
    #include
    
     #include
     
      using namespace std;const int N = 1010,M = 24010,INF = 0x3f3f3f3f;int n,m,s,t;int e[M],ne[M],w[M],f[M],h[N],idx;int pre[N],dis[N];bool vis[N];void add(int a,int b,int c,int d){
   	e[idx] = b;	w[idx] = d;	f[idx] = c;	ne[idx] = h[a];	h[a] = idx++;	e[idx] = a;	w[idx] = -d;	f[idx] = 0;	ne[idx] = h[b];	h[b] = idx++;}bool spfa()	//费用流模板{
   	queue
      
        q;	memset(dis,INF,sizeof dis);	memset(vis,0,sizeof vis);	memset(pre,-1,sizeof pre);	q.push(s);	dis[s] = 0;	while(q.size())	{
   		int u = q.front();		q.pop();		vis[u] = 0;		for(int i = h[u];~i;i = ne[i])		{
   			int v = e[i];			if(dis[v] > dis[u]+w[i] && f[i])			{
   				dis[v] = dis[u] + w[i];				pre[v] = i;				if(!vis[v])				{
   					vis[v] = 1;					q.push(v);				}			}		}	}	if(pre[t] != -1)		return 1;	else		return 0;}int EK(){
   	int cost = 0;	while(spfa())	{
   		int minf = INF;		for(int i = pre[t];~i;i = pre[e[i^1]])			minf = min(minf,f[i]);		for(int i = pre[t];~i;i = pre[e[i^1]])		{
   			f[i] -= minf;			f[i^1] += minf;			cost += minf * w[i];		}	}	return cost;}int main(){
   	cin >> n >> m;	s = 0,t = n+2;	memset(h,-1,sizeof h);	int last = 0;	for(int i = 1;i <= n;i++)	{
   		int cur;		cin >> cur;		if(last > cur)			add(s,i,last-cur,0);	//判断减去的下界那个小，然后和s或t连边，使得流量守恒		if(last < cur)			add(i,t,cur-last,0);		add(i,i+1,INF-cur,0);	//连接当前边和下一条边		last = cur;	}	add(s,n+1,last,0);	//最后一条边的cur为0，所以从s向i建容量为last的边	for(int i = 1;i <= m;i++)	{
   		int a,b,c;		cin >> a >> b >> c;		add(b+1,a,INF,c);	//从b+1向a连边，代表从第b天向第a天连的边，使人员流动	}	cout << EK() << endl;	//输出新图的最小费用最大流	 	return 0;}
      
     
    
   

转载地址：http://fbbki.baihongyu.com/