首页 > 代码库 > bzoj2039
bzoj2039
题意：作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。 作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？
思路：
把点集分成两个，很容易想到最小割模型。。
但是最小割求出来的是最少去掉的。。
所以我们想到了补集。。先所有都取然后去掉最少的。。
建图如下：
<S, i, sigma(E[i,j]) >
<i, T, a[i]>
<i, j, 2 * E[i][j]>
最后跑一遍最大流。。
答案即为sum(E[i][j]) - maxflow
code:
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/10/25 19:54:45 4 * File Name: bzoj2039.cpp 5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<cstring> 9 #include<cstdlib> 10 #include<cmath> 11 #include<algorithm> 12 #include<string> 13 #include<map> 14 #include<set> 15 #include<vector> 16 #define M0(a) memset(a, 0, sizeof(a)) 17 using namespace std; 18 typedef long long ll; 19 const int maxn = 1100; 20 const int Inf = 0x3fffffff; 21 const int maxm = 3100000; 22 struct oo{ 23 int y, next; 24 ll f; 25 }; 26 struct MaxFlow{ 27 int n, S, T, tot; 28 int son[maxn], dist[maxn], gap[maxn]; 29 oo e[maxm]; 30 ll sap(int x,ll aug){ 31 if (x == T) return aug; 32 int mind = n; 33 ll sum = 0, f; 34 for (int p = son[x]; p != -1; p = e[p].next){ 35 int y = e[p].y; 36 if (dist[y] + 1 == dist[x] && e[p].f){ 37 f = sap(y, min(e[p].f, aug - sum)); 38 e[p].f -= f; 39 e[p^1].f += f; 40 sum += f; 41 if (sum == aug || dist[S] >= n) return sum; 42 } 43 if (e[p].f) mind = min(mind, dist[y]); 44 } 45 if (!sum){ 46 if (!(--gap[dist[x]])) dist[S] = n; 47 ++gap[dist[x] = mind + 1]; 48 } 49 return sum; 50 } 51 52 void add(int x, int y, ll f){ 53 e[tot].y = y; e[tot].f = f; 54 e[tot].next = son[x]; son[x] = tot++; 55 e[tot].y = x; e[tot].f = 0; 56 e[tot].next = son[y]; son[y] = tot++; 57 } 58 59 void init(int S, int T, int n){ 60 memset(son, -1, sizeof(son)); 61 tot = 0; 62 this->S = S, this->T = T, this->n = n; 63 } 64 ll maxflow(){ 65 M0(gap); 66 M0(dist); 67 gap[0] = n; 68 ll ans = 0; 69 while (dist[S] < n) ans += sap(S, Inf); 70 return ans; 71 } 72 } F; 73 int a[1200], n, m; 74 ll s[1200]; 75 int e[1200][1200]; 76 void solve(){ 77 for (int i = 1; i <= n; ++i) 78 scanf("%d", &a[i]); 79 M0(s); 80 ll sum = 0; 81 for (int i = 1; i <= n; ++i){ 82 for (int j = 1; j <= n; ++j) 83 scanf("%d", &e[i][j]), s[i] += e[i][j], sum += e[i][j]; 84 } 85 int S = 0, T = n + 1; 86 F.init(S, T, T + 1); 87 for (int i = 1; i <= n; ++i) 88 F.add(S, i, a[i]), F.add(i, T, s[i]); 89 for (int i = 1; i <= n; ++i) 90 for (int j = 1; j <= n; ++j) if (i != j) 91 if (e[i][j] > 0) F.add(i, j, e[i][j] << 1); 92 sum -= F.maxflow(); 93 cout << sum << endl; 94 } 95 96 int main(){ 97 while (scanf("%d", &n) != EOF){ 98 solve(); 99 }100 return 0;101 }
bzoj2039
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。