搭配买卖题解

Ji-Siqi / 2023-08-19 / 原文

原题

题目描述

joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n多云，云朵被编号为1，2，……，n，并且每朵云都有一个价值。但商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这多云有搭配的云都要买。但是Joe 的钱有限，所以他希望买的价值越多越好。

输入

第1行：n、m、w，表示n多云，m个搭配，Joe有w的钱

第2至n+1行，每行ci，di表示i朵云的价钱和价值。

第n+2至n+1+m行，每行ui，vi表示买ui就必须买vi，同理，如果买vi就必须买ui。

输出

一行：表示可以获得的最大价值

样例

样例输入1

样例输出1

题意

有n个点，每个点有一个价钱ci和一个价值di。有m条边把其中的一些点相连。现在有w的钱，请问最多可以买多少价值的点。

思路

既然是有些点相连，那不就是求连通块、缩点吗？

缩完点后的SCC的价值是连通块内点的价值总和，价钱也是。

再用SCC来跑01背包

样例的图

实现

可以用并查集来储存，然后缩点:

for(int i=1; i<=n; i++) {
    int v=find(i);
    if(!vis[v]) {
        cnt++;
		vis[v]=cnt;
	}
	c[vis[v]]+=e[i].x;
	w[vis[v]]+=e[i].y;
}

以及我用Tarjan的做法:

//标准的Tarjan模板
void tarjan(int x) {
	dfn[x] = low[x] = ++num;
	vis[x] = 1;
	s[++top] = x;
	for (int y : g[x]) {
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (vis[y])
			low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x]) {
		int y;
		++cnt;
		do {
			y = s[top--];
			vis[y] = 0;
			c[y] = cnt;
		} while (y != x);
	}
}

完整代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;

int n, m, w, f1[N], f2[N], ans = 0;
vector <int> g[N];//存图
int dfn[N], low[N], vis[N], c[N], ff1[N], ff2[N];
int cnt, num, s[N], top;

//标准的Tarjan模板
void tarjan(int x) {
	dfn[x] = low[x] = ++num;
	vis[x] = 1;
	s[++top] = x;
	for (int y : g[x]) {
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (vis[y])
			low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x]) {
		int y;
		++cnt;
		do {
			y = s[top--];
			vis[y] = 0;
			c[y] = cnt;
		} while (y != x);
	}
}

int main() {
//	freopen("buy.in", "r", stdin);
//	freopen("buy.out", "w", stdout);
	int a, b;
	cin >> n >> m >> w;
	for (int i = 1; i <= n; i++) {
		cin >> f1[i] >> f2[i];
	}
    //读入
	while (m--) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) 
		if (!dfn[i]) 
			tarjan(i);
	for (int i = 1; i <= n; i++) 
		ff1[c[i]] += f1[i], ff2[c[i]] += f2[i], f1[i] = 0;
	for (int i = 1; i <= cnt; i++) 
		for (int j = w; j >= ff1[i]; j--) //01背包
			f1[j] = max(f1[j], f1[j - ff1[i]] + ff2[i]);
	cout << f1[w];

	return 0;
}