正文
[HAOI 2010]软件安装
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Description
现在我们的手头有N个软件,对于一个软件i,它要占用W
i
的磁盘空间,它的价值为V
i
。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即V
i
的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系:软件i依赖软件D
i
。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则D
i
=0,这时只要这个软件安装了,它就能正常工作。
Input
第1行:N, M (0<=N<=100, 0<=M<=500)
第2行:W
1
, W
2
, ... W
i
, ..., W
n
(0<=W
i
<=M )
第3行:V
1
, V
2
, ..., V
i
, ..., V
n
(0<=Vi<=1000 )
第4行:D
1
, D
2
, ..., D
i
, ..., D
n
(0<=D
i
<=N, D
i
≠i )
Output
一个整数,代表最大价值。
Sample Input
3 10
5 5 6
2 3 4
0 1 1
Sample Output
5
题解
比较裸的树上背包...只不过可能成环比较坑。
$tarjan$缩点之后再全部连向一个虚点,直接树形$DP$。
//It is made by Awson on 2017.11.5
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
using namespace std;
const int N = ;
const int M = ;
int n, m;
int W[N+], V[N+], w[N+], v[N+], d[N+];
struct tt {
int to, next;
}edge[N+];
int path[N+], top;
int dfn[N+], low[N+], cnt_time;
stack<int>S;
bool vis[N+], in[N+];
int sccno[N+], sccnum;
int f[N+][M+];
void tarjan(int x) {
dfn[x] = low[x] = ++cnt_time; S.push(x); vis[x] = ;
for (int i = path[x]; i; i = edge[i].next) {
if (vis[edge[i].to]) low[x] = Min(low[x], dfn[edge[i].to]);
else if (!dfn[edge[i].to]) {
tarjan(edge[i].to); low[x] = Min(low[x], low[edge[i].to]);
}
}
if (dfn[x] == low[x]) {
sccnum++; int u = -;
do {
u = S.top(); S.pop();
vis[u] = , sccno[u] = sccnum;
w[sccnum] += W[u], v[sccnum] += V[u];
}while (u != x);
}
}
void dfs(int u) {
for (int i = path[u]; i; i = edge[i].next) {
dfs(edge[i].to);
for (int j = m; j >= ; j--)
for (int k = ; k <= j; k++)
f[u][j] = Max(f[u][k]+f[edge[i].to][j-k], f[u][j]);
}
for (int i = m; i >= ; i--) {
if (i-w[u] >= ) f[u][i] = f[u][i-w[u]]+v[u];
else f[u][i] = ;
}
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &W[i]);
for (int i = ; i <= n; i++) scanf("%d", &V[i]);
for (int i = ; i <= n; i++) {
scanf("%d", &d[i]); add(d[i], i);
}
for (int i = ; i <= n; i++) if (!dfn[i]) tarjan(i);
memset(path, , sizeof(path)); top = ;
for (int i = ; i <= n; i++) if (sccno[i] != sccno[d[i]]) add(sccno[d[i]], sccno[i]), in[sccno[i]] = ;
for (int i = ; i <= sccnum; i++) if (!in[i]) add(, i);
dfs();
int ans = ;
for (int i = ; i <= m; i++) ans = Max(f[][i], ans);
printf("%d", ans);
}
int main() {
work();
return ;
}
现在我们的手头有N个软件,对于一个软件i,它要占用W
i
的磁盘空间,它的价值为V
i
。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即V
i
的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系:软件i依赖软件D
i
。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则D
i
=0,这时只要这个软件安装了,它就能正常工作。
第1行:N, M (0<=N<=100, 0<=M<=500)
第2行:W
1
, W
2
, ... W
i
, ..., W
n
(0<=W
i
<=M )
第3行:V
1
, V
2
, ..., V
i
, ..., V
n
(0<=Vi<=1000 )
第4行:D
1
, D
2
, ..., D
i
, ..., D
n
(0<=D
i
<=N, D
i
≠i )
Output
一个整数,代表最大价值。
Sample Input
3 10
5 5 6
2 3 4
0 1 1
Sample Output
5
题解
比较裸的树上背包...只不过可能成环比较坑。
$tarjan$缩点之后再全部连向一个虚点,直接树形$DP$。
//It is made by Awson on 2017.11.5
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
using namespace std;
const int N = ;
const int M = ;
int n, m;
int W[N+], V[N+], w[N+], v[N+], d[N+];
struct tt {
int to, next;
}edge[N+];
int path[N+], top;
int dfn[N+], low[N+], cnt_time;
stack<int>S;
bool vis[N+], in[N+];
int sccno[N+], sccnum;
int f[N+][M+];
void tarjan(int x) {
dfn[x] = low[x] = ++cnt_time; S.push(x); vis[x] = ;
for (int i = path[x]; i; i = edge[i].next) {
if (vis[edge[i].to]) low[x] = Min(low[x], dfn[edge[i].to]);
else if (!dfn[edge[i].to]) {
tarjan(edge[i].to); low[x] = Min(low[x], low[edge[i].to]);
}
}
if (dfn[x] == low[x]) {
sccnum++; int u = -;
do {
u = S.top(); S.pop();
vis[u] = , sccno[u] = sccnum;
w[sccnum] += W[u], v[sccnum] += V[u];
}while (u != x);
}
}
void dfs(int u) {
for (int i = path[u]; i; i = edge[i].next) {
dfs(edge[i].to);
for (int j = m; j >= ; j--)
for (int k = ; k <= j; k++)
f[u][j] = Max(f[u][k]+f[edge[i].to][j-k], f[u][j]);
}
for (int i = m; i >= ; i--) {
if (i-w[u] >= ) f[u][i] = f[u][i-w[u]]+v[u];
else f[u][i] = ;
}
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &W[i]);
for (int i = ; i <= n; i++) scanf("%d", &V[i]);
for (int i = ; i <= n; i++) {
scanf("%d", &d[i]); add(d[i], i);
}
for (int i = ; i <= n; i++) if (!dfn[i]) tarjan(i);
memset(path, , sizeof(path)); top = ;
for (int i = ; i <= n; i++) if (sccno[i] != sccno[d[i]]) add(sccno[d[i]], sccno[i]), in[sccno[i]] = ;
for (int i = ; i <= sccnum; i++) if (!in[i]) add(, i);
dfs();
int ans = ;
for (int i = ; i <= m; i++) ans = Max(f[][i], ans);
printf("%d", ans);
}
int main() {
work();
return ;
}
一个整数,代表最大价值。
3 10
5 5 6
2 3 4
0 1 1
5 5 6
2 3 4
0 1 1
Sample Output
5
题解
比较裸的树上背包...只不过可能成环比较坑。
$tarjan$缩点之后再全部连向一个虚点,直接树形$DP$。
//It is made by Awson on 2017.11.5
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
using namespace std;
const int N = ;
const int M = ;
int n, m;
int W[N+], V[N+], w[N+], v[N+], d[N+];
struct tt {
int to, next;
}edge[N+];
int path[N+], top;
int dfn[N+], low[N+], cnt_time;
stack<int>S;
bool vis[N+], in[N+];
int sccno[N+], sccnum;
int f[N+][M+];
void tarjan(int x) {
dfn[x] = low[x] = ++cnt_time; S.push(x); vis[x] = ;
for (int i = path[x]; i; i = edge[i].next) {
if (vis[edge[i].to]) low[x] = Min(low[x], dfn[edge[i].to]);
else if (!dfn[edge[i].to]) {
tarjan(edge[i].to); low[x] = Min(low[x], low[edge[i].to]);
}
}
if (dfn[x] == low[x]) {
sccnum++; int u = -;
do {
u = S.top(); S.pop();
vis[u] = , sccno[u] = sccnum;
w[sccnum] += W[u], v[sccnum] += V[u];
}while (u != x);
}
}
void dfs(int u) {
for (int i = path[u]; i; i = edge[i].next) {
dfs(edge[i].to);
for (int j = m; j >= ; j--)
for (int k = ; k <= j; k++)
f[u][j] = Max(f[u][k]+f[edge[i].to][j-k], f[u][j]);
}
for (int i = m; i >= ; i--) {
if (i-w[u] >= ) f[u][i] = f[u][i-w[u]]+v[u];
else f[u][i] = ;
}
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &W[i]);
for (int i = ; i <= n; i++) scanf("%d", &V[i]);
for (int i = ; i <= n; i++) {
scanf("%d", &d[i]); add(d[i], i);
}
for (int i = ; i <= n; i++) if (!dfn[i]) tarjan(i);
memset(path, , sizeof(path)); top = ;
for (int i = ; i <= n; i++) if (sccno[i] != sccno[d[i]]) add(sccno[d[i]], sccno[i]), in[sccno[i]] = ;
for (int i = ; i <= sccnum; i++) if (!in[i]) add(, i);
dfs();
int ans = ;
for (int i = ; i <= m; i++) ans = Max(f[][i], ans);
printf("%d", ans);
}
int main() {
work();
return ;
}
题解
比较裸的树上背包...只不过可能成环比较坑。
$tarjan$缩点之后再全部连向一个虚点,直接树形$DP$。
//It is made by Awson on 2017.11.5
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
using namespace std;
const int N = ;
const int M = ; int n, m;
int W[N+], V[N+], w[N+], v[N+], d[N+];
struct tt {
int to, next;
}edge[N+];
int path[N+], top;
int dfn[N+], low[N+], cnt_time;
stack<int>S;
bool vis[N+], in[N+];
int sccno[N+], sccnum;
int f[N+][M+]; void tarjan(int x) {
dfn[x] = low[x] = ++cnt_time; S.push(x); vis[x] = ;
for (int i = path[x]; i; i = edge[i].next) {
if (vis[edge[i].to]) low[x] = Min(low[x], dfn[edge[i].to]);
else if (!dfn[edge[i].to]) {
tarjan(edge[i].to); low[x] = Min(low[x], low[edge[i].to]);
}
}
if (dfn[x] == low[x]) {
sccnum++; int u = -;
do {
u = S.top(); S.pop();
vis[u] = , sccno[u] = sccnum;
w[sccnum] += W[u], v[sccnum] += V[u];
}while (u != x);
}
}
void dfs(int u) {
for (int i = path[u]; i; i = edge[i].next) {
dfs(edge[i].to);
for (int j = m; j >= ; j--)
for (int k = ; k <= j; k++)
f[u][j] = Max(f[u][k]+f[edge[i].to][j-k], f[u][j]);
}
for (int i = m; i >= ; i--) {
if (i-w[u] >= ) f[u][i] = f[u][i-w[u]]+v[u];
else f[u][i] = ;
}
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &W[i]);
for (int i = ; i <= n; i++) scanf("%d", &V[i]);
for (int i = ; i <= n; i++) {
scanf("%d", &d[i]); add(d[i], i);
}
for (int i = ; i <= n; i++) if (!dfn[i]) tarjan(i);
memset(path, , sizeof(path)); top = ;
for (int i = ; i <= n; i++) if (sccno[i] != sccno[d[i]]) add(sccno[d[i]], sccno[i]), in[sccno[i]] = ;
for (int i = ; i <= sccnum; i++) if (!in[i]) add(, i);
dfs();
int ans = ;
for (int i = ; i <= m; i++) ans = Max(f[][i], ans);
printf("%d", ans);
}
int main() {
work();
return ;
}