|
PIGS
Description Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold. More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses. An unlimited number of pigs can be placed in every pig-house. Write a program that will find the maximum number of pigs that he can sell on that day. Input The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000. The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line): A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0. Output The first and only line of the output should contain the number of sold pigs.
Sample Input 3 3 Sample Output 7 Source |
[Submit] [Go Back] [Status] [Discuss]
网络流——流量传递类型。
四月份的时候曾经写过一遍，但是已然忘光了，所以只得重新来过。
错误的建图方法
看到题之后有个简单的建图想法，就是设立M*N个猪圈点，以及N个商人点，如下建图：
源点向第一排M个猪圈点连容量为初始猪数目的边，代表一开始猪圈中最多存在的猪。
每排M个猪圈点中，A个能被打开的猪圈点向商人点连容量为无穷的边，代表可以被打开。
每排的商人点向汇点连容量为商人购买数目B的边，表示这个人的最大购买限度。
每排的商人点向下一排的A个点（这A个点还是本排商人能打开的猪圈）连无穷边，代表猪可以*转移。
当然，因为猪也可以待在猪圈里不动，所以每排的各个猪圈向下一排的该猪圈连无穷边。
这样跑最大流，显然可以得到最优解，但是点的数量是O(N*M)的，而边的数量是……（懒得想了），果不其然地TLE了。
#include <cstdio>
#include <cstring> inline int get_c(void)
{
static const int siz = ; static char buf[siz];
static char *head = buf + siz;
static char *tail = buf + siz; if (head == tail)
fread(head = buf, , siz, stdin); return *head++;
} inline int get_i(void)
{
register int ret = ;
register int neg = false;
register int bit = get_c(); for (; bit < ; bit = get_c())
if (bit == '-')neg ^= true; for (; bit > ; bit = get_c())
ret = ret * + bit - ; return neg ? -ret : ret;
} template <class T>
inline T min(T a, T b)
{
return a < b ? a : b;
} const int inf = 2e9;
const int maxn = ; int n, m;
int s, t;
int edges;
int hd[maxn];
int to[maxn];
int nt[maxn];
int fl[maxn]; inline void add(int u, int v, int f)
{ //printf("add %d %d %d\n", u, v, f);
nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++;
nt[edges] = hd[v]; to[edges] = u; fl[edges] = ; hd[v] = edges++;
} int dep[maxn]; inline bool bfs(void)
{
static int que[maxn];
static int head, tail; memset(dep, , sizeof(dep));
head = , tail = ;
que[tail++] = s;
dep[s] = ; while (head != tail)
{
int u = que[head++], v;
for (int i = hd[u]; ~i; i = nt[i])
if (!dep[v = to[i]] && fl[i])
{
dep[v] = dep[u] + ;
que[tail++] = v;
}
} return dep[t] != ;
} int dfs(int u, int f)
{
if (u == t || !f)
return f; int used = , flow, v; for (int i = hd[u]; ~i; i = nt[i])
if (dep[v = to[i]] == dep[u] + && fl[i])
{
flow = dfs(v, min(f - used, fl[i])); used += flow;
fl[i] -= flow;
fl[i^] += flow; if (used == f)
return f;
} if (!used)
dep[u] = ; return used;
} inline int maxFlow(void)
{
int maxFlow = , newFlow; while (bfs())
while (newFlow = dfs(s, inf))
maxFlow += newFlow; return maxFlow;
} signed main(void)
{
n = get_i();
m = get_i(); s = , t = (n + ) * m + ; memset(hd, -, sizeof(hd)); for (int i = ; i <= n; ++i)
{
int pigs = get_i();
add(s, i, pigs);
} for (int i = ; i < m; ++i)
for (int j = ; j <= n; ++j)
add((n + )*(i - ) + j, (n + )*i + j, inf); for (int i = ; i <= m; ++i)
{
int k = get_i();
for (int j = ; j <= k; ++j)
{
int p = get_i();
add((n + )*(i - ) + p, (n + )*i, inf);
add((n + )*i, (n + )*i + p, inf);
}
add((n + )*i, t, get_i());
} printf("%d\n", maxFlow());
}
正确的建图方法
设置一个源点，向M个猪圈点连初始数目的边，代表一开始的猪的数目。
然后想办法简化猪圈之间的转移，着重商人能得到的猪的来源，考虑直接在商人之间进行转移。
易知，如果商人X和商人Y，有X比Y先来，且X和Y有公共的猪圈的钥匙，那么Y能享受X能到达的所有猪圈。
用last_i表示上一个可以打开i猪圈的点，初始last_i=i猪圈初始点。
一个商人，如果有猪圈k的钥匙，那么last_k的所有流量都可以向这个商人转移，所有从last_k向商人连边，同时把last_k设为该商人。
商人点向汇点连最大购买数量的边。
跑最大流即可，点数O(N+M)，边数O(N+M)，小菜一碟了。
#include <cstdio>
#include <cstring> inline int get_c(void)
{
static const int siz = ; static char buf[siz];
static char *head = buf + siz;
static char *tail = buf + siz; if (head == tail)
fread(head = buf, , siz, stdin); return *head++;
} inline int get_i(void)
{
register int ret = ;
register int neg = false;
register int bit = get_c(); for (; bit < ; bit = get_c())
if (bit == '-')neg ^= true; for (; bit > ; bit = get_c())
ret = ret * + bit - ; return neg ? -ret : ret;
} template <class T>
inline T min(T a, T b)
{
return a < b ? a : b;
} const int inf = 2e9;
const int maxn = ; int n, m;
int s, t;
int edges;
int hd[maxn];
int to[maxn];
int nt[maxn];
int fl[maxn]; inline void add(int u, int v, int f)
{ //printf("add %d %d %d\n", u, v, f);
nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++;
nt[edges] = hd[v]; to[edges] = u; fl[edges] = ; hd[v] = edges++;
} int dep[maxn]; inline bool bfs(void)
{
static int que[maxn];
static int head, tail; memset(dep, , sizeof(dep));
head = , tail = ;
que[tail++] = s;
dep[s] = ; while (head != tail)
{
int u = que[head++], v;
for (int i = hd[u]; ~i; i = nt[i])
if (!dep[v = to[i]] && fl[i])
{
dep[v] = dep[u] + ;
que[tail++] = v;
}
} return dep[t] != ;
} int dfs(int u, int f)
{
if (u == t || !f)
return f; int used = , flow, v; for (int i = hd[u]; ~i; i = nt[i])
if (dep[v = to[i]] == dep[u] + && fl[i])
{
flow = dfs(v, min(f - used, fl[i])); used += flow;
fl[i] -= flow;
fl[i^] += flow; if (used == f)
return f;
} if (!used)
dep[u] = ; return used;
} inline int maxFlow(void)
{
int maxFlow = , newFlow; while (bfs())
while (newFlow = dfs(s, inf))
maxFlow += newFlow; return maxFlow;
} int last[maxn]; signed main(void)
{
n = get_i();
m = get_i(); s = , t = n + m + ; memset(hd, -, sizeof(hd)); for (int i = ; i <= n; ++i)
add(s, i, get_i()), last[i] = i; for (int i = ; i <= m; ++i)
{
for (int j = get_i(), k; j--; )
k = get_i(), add(last[k], n + i, inf), last[k] = n + i;
add(n + i, t, get_i());
} printf("%d\n", maxFlow());
}
@Author: YouSiki