搭配买卖题解

jsq in 题解 · Views

洛谷原题链接

题意

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

思路

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

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

再用 SCC 来跑 01背包

图1

实现

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

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;
}