NC14545. 经商
描述
小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。
小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。
小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。
小d想知道，他在精力范围内，能够获得的利益值到底是多少。
设定小d自己的编号为1.并且对应一个人的交际次数限定为1.
输入描述
本题包含多组输入，第一行输入一个数t，表示测试数据的组数
每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值
接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人交际需要花费ai的精力，能够获得的利益值为bi。
再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai，bi<=10
1<=C<=500
1<=x,y<=N
输出描述
输出包含一行，表示小d能够获得的最大利益值
示例1
输入:
1 5 3 7 5 10 3 2 4 3 1 100 1 2 2 3 1 4
输出:
10
C++(g++ 7.5.0) 解法, 执行用时: 32ms, 内存消耗: 520K, 提交时间: 2023-01-16 09:40:54
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[510];
const int maxn=1e4+10;
int f[maxn],a[maxn],b[maxn];
int find(int i){
return f[i]==i?f[i]:f[i]=find(f[i]);
}
int main()
{
int t,n,m,c,x,y;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=2;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=m;i++)
{
cin>>x>>y;
f[find(x)]=find(y); //简易合并操作
}
for(int i=2;i<=n;i++)
{
if(find(i)==find(1))
{
for(int j=c;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
cout<<dp[c]<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 472K, 提交时间: 2020-02-29 23:47:18
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e4;
int w[MAX],v[MAX],p[MAX],d[600];
int f(int x)
{
return p[x]==x?x:p[x]=f(p[x]);
}
int main()
{
int T,n,m,c;
cin>>T;
while(T--)
{
cin>>n>>m>>c;
memset(d,0,sizeof d);
for(int i=2;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(int i=1;i<=n;i++)
p[i]=i;
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
p[f(x)]=f(y);
}
for(int i=2;i<=n;i++)
{
if(f(1)!=f(i)) continue;
for(int j=c;j>=w[i];j--)
d[j]=max(d[j],d[j-w[i]]+v[i]);
}
cout<<d[c]<<endl;
}
return 0;
}