思路

这道题的解法是最小费用最大流。具体算法的原理可以去百度学习。这道题主要讨论如何对图进行建模。

我们发现一共N个人，每个人都有想去的地方，然后题意要我们保证N个人都能满足要求，然而每个地方都有人数限制。那么从这一个题意出发，很容易想到网络流的解法。

定义源点$S = 0$， 汇点$T= n + 4$

$N$个人，我们定义点为$[1,n]$,3个地方，我们定义点为$[n+1,n+3]$.

由于每个人最后只能去一个地方，所以我们将源点和每个人建立一条容量为1，费用为0的边。

由于每个地方最后最多只能容纳$lim[i]$个人，所以将每个地方与汇点建立一条容量为$lim[i]$， 费用为0的边。

由于每个人都有想去的地方，那么我们对每个人分别与他们想去的地方建立一条容量为1，费用为$cost[i]$的边。

最后我们只要求源点到汇点的最小费用最大流就像。

如果最大流等于人数，说明每个人可以被满足，此时输出最小费用即可。

如果不等于，那么最大流就是最多可以满足的人数。

要学习网络流，要理解这道题需要前置学习图论建边（链式前向星），spfa求最短路，最小费用最大流。周期比较长，建议只需要记住如何建图即可。

代码

#include<bits/stdc++.h>
#define mem(x, i) memset(x, i, sizeof x)
#define Next(i, u) for(int i=head[u];~i;i=edge[i].next)
using namespace std;
const int MAXN = 100 + 5;
const int MAXM = 5e4 + 5;
const int INF = 0x3f3f3f3f;
int n, cnt = 0;
int maxflow = 0, maxcost = 0;
int head[MAXN], dis[MAXN], inq[MAXN], pre[MAXN], last[MAXN];//head是每个点的第一条边在edge数组的位置，dis数组是最小费用数组，inq是spfa
//需要的用来判断一个点在不在队列里面。pre和last数组一起使用用来表现spfa求得的一条路径
int flow[MAXN];//记录最后的最大流
string strs[MAXN];
struct Edge{//图的边结构体
    int to, next;
    int c, w;
}edge[MAXM];
void addedge(int u, int v, int c, int w){//网络流建边，采用链式前向星的建边方法
    edge[cnt] = {v, head[u], c, w}; head[u] = cnt++;
    edge[cnt] = {u, head[v], 0, -w}; head[v] = cnt++;
}
bool spfa(int s, int t){//spfa求最小费用
	mem(dis, 0x3f);
	mem(flow, 0x3f);
	mem(inq, 0);//每次spfa都要初始化
	queue<int>q;
	q.push(s);
	dis[s] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		inq[u] = 0;
		Next(i, u){
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].w && edge[i].c > 0){
				dis[v] = dis[u] + edge[i].w;
				flow[v] = min(edge[i].c, flow[u]);
				pre[v] = u;
				last[v] = i;
				if(!inq[v]){
					q.push(v);
					inq[v] = 1;
				}
			}
		}
	}
	return dis[t] != INF;
}
void MCMF(int s, int t){
	while(spfa(s, t)){//对于得到的路径进行网络流
		maxcost += flow[t] * dis[t];
		maxflow += flow[t];
		int u = t;
		while(u != s){
			edge[last[u]].c -= flow[t];
			edge[last[u] ^ 1].c += flow[t];
			u = pre[u]; 
		}
	}
}
int main(){
	cin >> n;
	for(int i = 0; i <= n + 4; i++)head[i] = -1;
	cnt = 0;
	int lim[4], cost[4];
	for(int i = 1; i <= n; i++){
		cin >> strs[i];
	}
	for(int i = 1; i <= 3; i++){
		cin >> lim[i] >> cost[i];
		addedge(i + n, n + 4, lim[i], 0);//建立每个地方的边
	}
	for(int i = 1; i <= n; i++){
		addedge(0, i, 1, 0);//建立每个人的边
		for(int j = 0; j < strs[i].length(); j++){
			int tar = strs[i][j] - 'A' + 1;
			addedge(i, n + tar, 1, cost[tar]);//建立每个人与每个地方之间的边
		}
	}
	MCMF(0, n + 4);//求最小费用最大流
	if(maxflow != n){
		cout << "NO" << endl;
		cout << maxflow << endl;
	}else{
		cout << "YES" << endl;
		cout << maxcost << endl;
	}
}

题目内容

小红是公司里的一名领导，他负责组织今年的团建活动。这个团建活动很重要，因为公司里的员工们都非常忙碌，很少有机会聚在一起，所以这次活动是大家期待已久的。

为了让所有人都能够参加到自己想要参加的活动，小红收集了所有人的意愿，并准备了三个不同的活动：$A$、$B$ 和 $C$，每个活动都有不同的人数上限和参加费用。

为了让所有人都能参加到自己想要参加的活动，小红收集了所有人的投票结果。现在他希望在满足所有人的意愿的前提下，尽可能地降低团建的总费用。

但是，小红面临着一个难题，因为人们的意愿各不相同，他需要考虑每个人的选择，才能做出最好的决策。

因此，他找到了你，希望你能够帮助他找到一个最佳的团建方案，以让大家都能开心参与，并且尽可能地降低费用。

输入描述

第一行，一个整数 $N$ ，代表准备参加活动的人数。（ $1\le N\le 100$ ）

接下来 $N$ 行，每行一个由 "ABC" 组成的字符串，其中第 $i$ 行表示第 $i$ 个人投票了哪几个活动。（输入保证字符串非空，且由大写的 "ABC" 字符组成）

最后 $3$ 行，每行两个整数，分别表示三个活动的人数上限以及每个人参加的费用。（人数上限以及参与活动的费用均为不超过 $100$ 的正整数）

输出描述

输出共 $2$ 行

如果能满足所有人的要求，第一行输出 "YES" ，第二行输出最少的总费用。

如果不能满足所有人的要求，第一行输出 "NO" ，第二行输出最多能满足多少人。

样例

样例一

输入

5
A
B
C
AB
ABC
2 1
2 2
2 3

输出

YES
9

样例解释

可以满足所有人的要求，其中一种费用最少的方案:

A：{ $1，4$ }

B：{ $2，5$ }

C：{ $3$ }

总共需要费用：$1*2+2*2+3*1=9$

样例二

输入

5
A
B
C
AB
AB
1 1
2 2
3 3

输出

NO
4

样例解释

无法满足所有人的需求，其中一种满足最多人的方案： A：{ $1$ } B：{ $2，4$ } 3：{ $3$ } 共 $4$ 人