hdu4322（*最小费用流）

时间：2023-02-03 07:46:30
/*
translation:
n颗糖果，m个孩子。每个孩子有若干个自己喜欢的糖果。一旦这个孩子得到一颗自己喜欢的糖果，这个孩子的欢乐值上升k。如果
得到一颗普通的糖果，欢乐值上升1，一旦孩子的欢乐值达到b[i]，这个孩子就很开心。问能否有一种分配方法，使得所有的孩子
开心？
solution:
网络最小费用流
note:
* 由于边费用1的不好处理，所以可以i先处理边费用为k的，再上面跑最大流最小费用，即先用喜欢的糖果分配给孩子。
  然后判断剩下的糖果是否能填充满足孩子缺少的糖果数量即可。
* 在孩子喜欢的糖果和该孩子之间连接一条容量1,费用0的边。在每个糖果和源点之间添加容量1,费用0的边。
  在每个孩子和汇点之间添加容量b[i]/k，费用k的边，如果此时b[i] % k > 1，就再次添加一条容量1,
  费用b[i]%k的边。因为如果等于1,就不必用喜欢糖果来填充了，用一般糖果效果一样。再跑一遍最大流即可。
# 注意孩子和汇点间的第二条边连接时，费用是b[i]%k，因为如果是k的话，在最后判断时相当于“会将多出来的那部分喜悦值”
  分给别的孩子。但实际上多出来那部分是浪费的，所以正确的是添加费用为b[i]%k的边。
# 注意这道题需要将最小费用流模板稍微修改，因为事先是不知道最大流是多少？具体修改的方法见代码。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>

using namespace std;
const int maxn = 100;
const int INF = 0x3f3f3f3f;

struct Edge
{
int to, cap, cost, rev;
Edge(int to_, int cap_, int cost_, int rev_):to(to_),cap(cap_),cost(cost_),rev(rev_){}
};
int V, n, m, k, like[maxn][maxn], b[maxn];
vector<Edge> G[maxn];
int dist[maxn], prevv[maxn], preve[maxn];

void add_edge(int from, int to, int cap, int cost)
{
G[from].push_back(Edge(to, cap, cost, G[to].size()));
G[to].push_back(Edge(from, 0, -cost, G[from].size()-1));
}

void min_cost_flow(int s, int t, int& f, int& res)
{
res = f = 0;
for(;;) {
fill(dist, dist + V, INF);
dist[s] = 0;
bool update = true;
while(update) {
update = false;
for(int v = 0; v < V; v++) {
if(dist[v] == INF)continue;
for(int i = 0; i < G[v].size(); i++) {
Edge& e = G[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if(dist[t] == INF)break;

int d = INF;
for(int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
f += d;
res += d * dist[t];
for(int v = t; v != s; v = prevv[v]) {
Edge& e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
}

int main()
{
//freopen("in.txt", "r", stdin);
    int T, kase = 0;
    scanf("%d", &T);
    while(T--) {
for(int i = 0; i < maxn; i++)G[i].clear();
memset(like, 0, sizeof(like));

scanf("%d%d%d", &n, &m, &k);//n candies, m kids

int sum = 0;
for(int i = 0; i < m; i++) {
scanf("%d", &b[i]);
sum += b[i];
}

for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &like[i][j]);
}
}

//candies:0~n-1, kids:n~n+m-1
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(like[j][i])add_edge(i, j + n, 1, 0);
}
}

int s = n + m, t = s + 1;
for(int i = 0; i < n; i++)
add_edge(s, i, 1, 0);

for(int i = 0; i < m; i++) {
add_edge(i + n, t, b[i] / k, -k);
if(b[i] % k > 1)add_edge(i + n, t, 1, -(b[i] % k));
}

V = t + 1;
int f, res;//最大流和最小费用
min_cost_flow(s, t, f, res);
if(n - f >= sum + res)printf("Case #%d: YES\n", ++kase);
elseprintf("Case #%d: NO\n", ++kase);
    }
    return 0;
}

标签：

相关文章