NOI2008 & Acwing 969：志愿者招募（特殊的建图与无源汇|上下界|最小费用|可行流）

谁借莪１个温暖的怀抱￠ 2022-11-05 08:46 112阅读 0赞

### 题目链接 ###

传送门：[Acwing 969：志愿者招募][Acwing 969]

### 题目大意 ###

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

### 思路 ###

我们把这n天的每一天看作一条边，流量就是志愿者，每天的边都有个流量下界即每天所需的最少人数。然后现在要满足第Si天到第Ti天这些人的流动，我们从Ti\+1点向Si点连一条容量为正无穷，费用为Ci的边，就满足了这一类志愿者在Si到Ti天间流动，并且还满足了流量守恒，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]  
然后我们看代表天的这些边的**下界**分别是Ai（最少需要的人数），**上界**是正无穷（人数可以无限多）。所以我们就要按照处理[无源汇上下界可行流][Link 1]的方法来求一个可行流：我们给**每条边都减去他的下界**，然后为了使**流量守恒**，我们要判断上一条边减去的下界（Ai-1）和该边减去的下界（Ai）的大小，我们将Ai-1记作last，Ai记作cur，如果last > cur，就从s向i连一条容量为last - cur，费用为0的边；如果last < cur，就从i向t连一条容量为cur - last，费用为0的边。这样子所得的新图G’的满流就是原图G的一个可行流，因为所有有费用的边只有Ti\+1到Si的边（红边），且这些边和原图的边都相同（因为流量下界是0，相当于没减），所以新图G’的费用和原图G的费用一样，所以在新图上求个最小费用最大流就是问题的解。

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

### 代码详解 ###

#include<iostream>
    #include<queue>
    #include<cstring>
    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<int> 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;
    }

[Acwing 969]: https://www.acwing.com/problem/content/971/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20221023/95015a78ca3d4006a0b556853a128422.png
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/109717899