Clever King
Description
In order to increase the happiness index of people's lives, King Y has decided to develop the manufacturing industry vigorously. There are total n kinds of products that King can choose to produce, different products can improve the happiness index of poeple's lives in different degrees, of course, the production of goods needs raw materials, different products need different ore or other products as raw materials. There are total m mines, and each mine can exploit different ore, Therefore, there are m types of ores, the cost of each mining for each mine is different, king Y want to maximize the income, the calculation method of income is:∑increased happiness index - ∑mining costs.
If you choose to exploit a mine, there will be an unlimited number of this kind of ore. What's more, if you produce one product, the happiness index will definitely increase, no matter how many you produce.
Input
The first line of the input has an integer T(1<=T<=50), which represents the number of test cases.
In each test case, the first line of the input contains two integers n(1<=n<=200)--the number of the products and m(1<=m<=200)--the number of mines. The second line contains n integers, val[i] indicates the happiness index that number i product can increase. The third line contains m integers, cost[i] indicates the mining cost of number i mine. The next n lines, each line describes the type of raw material needed for the number i product, in each line, the first two integers n1(1<=n1<=m)--the number of ores that this product needs, n2(1<=n2<=n)--the number of products that this product needs, the next n1 + n2 integers indicate the id of ore and product that this product needs. it guarantees that ∑n1+∑n2<=2000.
Output
Each test case output an integer that indicates the maximum value ∑val[i]-∑cost[i].
忽略每行输出的末尾多余空格
样例输入
2
3 3
600 200 400
100 200 300
1 2 1 2 3
1 0 2
1 0 3
3 4
600 400 200
100 200 300 1000
2 1 1 2 3
1 0 1
1 0 1样例输出
600
900题目来源
链接
https://nanti.jisuanke.com/t/26172
题意&题解
最大权闭合子图，用最小割解决，建立源点S，向每个产品建一条流量为该产品价值的边，建立汇点T，每个矿场向汇点建立一条流量为该矿场开采成本的边，中间产品与产品，产品与矿场的依赖关系，如果a依赖b，则建立一条a向b的流量为正无穷的边，跑一边最大流，求出来的就是该图的最小割，用∑v[i] - 最小割就是答案。
注意：需要使用long long。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 200010;
int N, M;
const int inf = 0x3f3f3f3f;
struct Edge
{
int u, v, cap;
Edge() {}
Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
} es[maxn];
int R, S, T;
vector<int> tab[maxn]; // 边集
int dis[maxn];
int current[maxn];
void addedge(int u, int v, int cap)
{
tab[u].push_back(R);
es[R++] = Edge(u, v, cap); // 正向边
tab[v].push_back(R);
es[R++] = Edge(v, u, 0); // 反向边容量为0
// 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2
}
int BFS()
{
queue<int> q;
q.push(S);
memset(dis, 0x3f, sizeof(dis));
dis[S] = 0;
while (!q.empty())
{
int h = q.front();
q.pop();
for (int i = 0; i < tab[h].size(); i++)
{
Edge &e = es[tab[h][i]];
if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
{
dis[e.v] = dis[h] + 1;
q.push(e.v);
}
}
}
return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}
int dinic(int x, int maxflow)
{
if (x == T)
return maxflow;
// i = current[x] 当前弧优化
for (int i = current[x]; i < tab[x].size(); i++)
{
current[x] = i;
Edge &e = es[tab[x][i]];
if (dis[e.v] == dis[x] + 1 && e.cap > 0)
{
int flow = dinic(e.v, min(maxflow, e.cap));
if (flow)
{
e.cap -= flow; // 正向边流量降低
es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加
return flow;
}
}
}
return 0; // 找不到增广路 退出
}
long long DINIC()
{
long long ans = 0;
while (BFS()) // 建立分层图
{
int flow;
memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组
while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广
ans += flow;
}
return ans;
}
int main()
{
int kase;
scanf("%d", &kase);
while (kase--)
{
scanf("%d%d", &N, &M);
long long sum = 0;
R = 0;
S = 0, T = N + M + 1;
for (int i = 0; i <= T; i++)
tab[i].clear();
for (int i = 1; i <= N; i++)
{
int cap;
scanf("%d", &cap);
addedge(S, i, cap);
sum += cap;
}
for (int i = 1; i <= M; ++i)
{
int cap;
scanf("%d", &cap);
addedge(N + i, N + M + 1, cap);
}
for (int i = 1; i <= N; i++)
{
int u, n1, n2;
scanf("%d%d", &n1, &n2);
while (n1--)
{
scanf("%d", &u);
addedge(i, N + u, inf);
}
while (n2--)
{
scanf("%d", &u);
addedge(i, u, inf);
}
}
printf("%lld\n", sum - DINIC());
}
return 0;
}又一道模板题。
The end.
2018-05-02 星期三