原文地址：http://www.cnblogs.com/GXZlegend/p/6809670.html

---

題目描述

【背景】 坑校準備鼓勵學生參加學習小組。 【描述】 共有n個學生，m個學習小組，每個學生有一定的喜好，只愿意參加其中的一些學習小組，但是校領導為學生考慮，規定一個學生最多參加k個學習小組。財務處的大叔就沒那么好了，他想盡量多收錢，因為每個學生參加學習小組都要交一定的手續費，不同的學習小組有不同的手續費。然而，事與愿違，校領導又決定對學習小組組織者進行獎勵，若有a個學生參加第i個學習小組，那么給這個學習小組組織者獎勵Ci*a^2元。在參與學生（而不是每個學習小組的人數總和）盡量多的情況下，求財務處最少要支出多少錢（若為負數，則輸出負數）（支出=總獎勵費-總手續費）。

輸入

輸入有若干行，第一行有三個用空格隔開的正整數n、m、k。接下來的一行有m個正整數，表示每個Ci。第三行有m個正整數，表示參加每個學習小組需要交的手續費Fi。再接下來有一個n行m列的矩陣，表若第i行j列的數字是1，則表示第i個學生愿意參加第j個學習小組，若為0，則為不愿意。

輸出

輸出只有一個整數，為最小的支出。

樣例輸入

3 3 1
1 2 3
3 2 1
111
111
111

樣例輸出

-2

---

題解

拆邊+費用流

由于有Ci*a^2的存在，使得正常加邊的費用流無法處理。我們可以加容量為1，費用為Ci*1、Ci*3、Ci*5、Ci*7、...的一堆邊，這樣在最小費用的前提下總花費滿足題意。

每個學習小組向T連上述所說的邊，S向每個學生連一條容量為k，費用為0的邊，每個學生向其能參加的學習小組連一條容量為1，費用為Fi的邊。

因為題目中描述“在參與學生（而不是每個學習小組的人數總和）盡量多的情況下”，指的是所有學生必須有流通過，但不必滿流。

所以還要從每個學生向T連一條容量為k-1，費用為0的邊，保證費用最小。

然后跑最小費用最大流即可。

#include <cstdio> #include <cstring> #include <queue> using namespace std; queue<int> q; int f[110] , head[210] , to[100000] , val[100000] , cost[100000] , next[100000] , cnt = 1 , s , t , dis[210] , from[210] , pre[210]; char str[110]; void add(int x , int y , int v , int c) {to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt; } bool spfa() {int x , i;memset(dis , 0x3f , sizeof(dis));memset(from , -1 , sizeof(from));dis[s] = 0 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i])if(val[i] && dis[to[i]] > dis[x] + cost[i])dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);}return ~from[t]; } int mincost() {int i , k , ans = 0;while(spfa()){k = 0x3f3f3f3f;for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);ans += k * dis[t];for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;}return ans; } int main() {int n , m , k , i , j , x;scanf("%d%d%d" , &n , &m , &k);s = 0 , t = n + m + 1;for(i = 1 ; i <= m ; i ++ ){scanf("%d" , &x);for(j = 1 ; j <= n ; j ++ ) add(i + n , t , 1 , x * (2 * j - 1));}for(i = 1 ; i <= m ; i ++ ) scanf("%d" , &f[i]);for(i = 1 ; i <= n ; i ++ ){add(s , i , k , 0) , add(i , t , k - 1 , 0);scanf("%s" , str + 1);for(j = 1 ; j <= m ; j ++ )if(str[j] == '1')add(i , j + n , 1 , -f[j]);}printf("%d\n" , mincost());return 0; }

?

轉載于:https://www.cnblogs.com/GXZlegend/p/6809670.html

總結

以上是生活随笔為你收集整理的【bzoj3442】学习小组 费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。