[LSGDOJ 1299]搭配买卖

题目描述

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

输入

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

第二只n+1行，每行ci，di表示i朵云的价钱和价值

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

输出

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

样例输入

5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2

样例输出

1

提示

n<=10000,m<=5000,w<=10000

题解：

此题很水，但是我却看错了题目，想到了另一种题目类型决定把这种也说说.

先讲此题：

这题意是有关联的要买就都买，于是用并查集合并，然后背包.

接下来是另一种：

我以为是拓扑序，买完这个就不买他的下层.

也就是说1->2->3可以只买2.3不买1

于是想到dfs一边，把所有的购买方案都看作一个物品（3，23，123）然后再背包

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int gi(){

     int str=;char ch=getchar();

     while(ch>'' || ch<'')ch=getchar();

     while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();

     return str;

 }

 struct node{

     int w,val;

 }a[N];

 int fa[N],F[N];

 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

 int w[N],v[N],tot=;

 int main()

 {

     //freopen("pp.in","r",stdin);

     int n=gi(),m=gi(),k=gi(),x,y;

     for(int i=;i<=n;i++)a[i].w=gi(),a[i].val=gi(),fa[i]=i;

     for(int i=;i<=m;i++)

     {

         x=gi();y=gi();

         a[find(x)].val+=a[find(y)].val;

         a[find(x)].w+=a[find(y)].w;

         fa[find(y)]=find(x);

     }

     for(int i=;i<=n;i++)if(fa[i]==i){w[++tot]=a[i].w;v[tot]=a[i].val;}

     for(int i=;i<=tot;i++)

     {

         for(int j=k;j>=w[i];j--)

         {

             F[j]=max(F[j-w[i]]+v[i],F[j]);

         }

     }

     printf("%d",F[k]);

     return ;

 }