「vijos1250」最勇敢的机器人
背景
Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了~
描述
机器人们都想知道谁是最勇敢的，于是它们比赛搬运一些物品。
它们到了一个仓库，里面有n个物品，每个物品都有一个价值Pi和重量Wi，但是有些物品放在一起会爆炸，并且爆炸具有传递性。（a和b会爆炸、b和c会爆炸则a和c会爆炸）
机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备，于是它们想知道在能力范围内，它们最多可以拿多少价值的物品。
你能帮助它们吗？
输入格式
每组测试数据
第1行为n,Wmax,k(0<=n,Wmax,k<=1000)
接下来n行，为每个物品的Pi,Wi(0<=Pi<=1000,1<=Wi<=10,均为整数)
再接下来k行，每行2个数字a,b表示a和b会发生爆炸
输出格式
对每组数据输出1行
为最大可能价值
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstring> using namespace std; int w[1001],c[1001]; int father[1001],ans=0; int n,mv,m; int fz=0; int s[1001],a[1001][1001],f[1001]; int find(int x) { if(x!=father[x])father[x]=find(father[x]); return father[x]; } void un(int x,int y) { int a=find(x),b=find(y); if(a!=b)father[a]=b; } void wk(int x) { for(int i=1;i<=fz;i++) if(a[i][0]==find(x)){s[i]++;a[i][s[i]]=x;return;} fz++; s[fz]=1; a[fz][s[fz]]=x; a[fz][0]=find(x); } int main() { cin>>n>>mv>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; un(x,y); } for(int i=1;i<=n;i++) wk(i); for(int i=1;i<=fz;i++) for(int v=mv;v>=0;v--) for(int k=1;k<=s[i];k++) if(v-w[a[i][k]]>=0)f[v]=max(f[v],f[v-w[a[i][k]]]+c[a[i][k]]); cout<<f[mv]; return 0; } |
Subscribe
计数器 9850861
OI 课件=>
OI 课件=>