为什么用 DFS 缩点就不行?
查看原帖
为什么用 DFS 缩点就不行?
490484
include13_fAKe楼主2024/3/24 17:08
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct node{
	int u_;//价值 
	int v_;//魅力 
}p[1005]; 
int N,M,W;
int w[1005];
int b[1005];
int a;//team_stamp
int b_;
int U,V;
int team[1005];
int dp[1005][1005];
vector<int> g[1005];
void search(int u){
	team[u]=a;
//	cout<<u<<' '<<a<<endl;
	b_++;
	p[b_].u_=w[u];
	U+=w[u];
	V+=b[u]; 
	p[b_].v_=b[u];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!team[v])	search(v);
	}
	return;
}
int main(){
	cin>>N>>M>>W;
	for(int i=1;i<=N;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=N;i++){
		scanf("%d",&b[i]);
	}
	for(int i=1;i<=M;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=N;i++){
		if(!team[i]){
			a++;
			b_=0;
			U=V=0;
			search(i);
			b_++;
			p[b_].u_=U;
			p[b_].v_=V;
		} 
		for(int j=1;j<=W;j++){
			dp[a][j]=dp[a-1][j];
			for(int k=1;k<=b_;k++){
				if(j>=p[k].u_){
					dp[a][j]=max(dp[a][j],dp[a-1][j-p[k].u_]+p[k].v_);
				}
			}
		}
	}
//	cout<<a<<endl;
	cout<<dp[a][W]<<endl;
	return 0;
}
2024/3/24 17:08
加载中...