CSU 1326: The contest（分组背包）

用户1624346

发布于 2018-04-17 16:25:14

5820

发布于 2018-04-17 16:25:14

文章被收录于专栏：calmound calmoundcalmound

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326

题意：

n个题目，每个题目都有一个价值Pi和相对能力消耗Wi，但是有些题目因为太坑不能同时做出来，并且坑题具有传递性。（a和b一起做会坑、b和c会坑则a和c也会坑）它们最多可以作出多少价值的题目。

分析：先用并查集，将组分出来，然后进行分组背包

注意F数组，数组开辟的大小应该为总价值的最大值，还有初始化别忘记了

以及j-pi[i]>=0 一维数组：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
const int MOD=1000000007;
const int MN=1010;
int father[MN];
int num[MN][MN];
int rank[MN];
int f[MN];
int val[MN],pi[MN];
int vis[MN];
int cnt[MN];
 
void Make_set(int n)
{
    for(int i=0; i<=n; i++)
    {
        father[i]=i;
    }
}
 
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
 
void Union(int x,int y)
{
    if(x==y) return ;
    father[x]=y;
}
 
int main()
{
    int i,j,k,n,m;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Make_set(n);
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&val[i],&pi[i]);
        }
        int a,b;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&a,&b);
            int x=Find(a);
            int y=Find(b);
            Union(x,y);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            int t=Find(i);
            vis[t]++;
        }
        int cas=0;
        for(i=1; i<=n; i++)
        {
            if(vis[i])
            {
                ++cas;
                int tes=0;
                for(j=1; j<=n; j++)
                {
                    if(father[j]==i)
                        num[cas][++tes]=j;
                }
                cnt[cas]=vis[i];
            }
        }
        memset(f,0,sizeof(f));
        for(i=1;i<=cas;i++)
        {
            for(j=m;j>=0;j--)
            {
                for(k=1;k<=cnt[i];k++)
                {
                    int xx=num[i][k];
                    if(j-pi[xx]>=0) f[j]=max(f[j],f[j-pi[xx]]+val[xx]);
                }
            }
        }
        printf("%d\n",f[m]);
    }
    return 0;
}

二维数组：

循环取最大值的那里要小心，始终要和f[i-1][j]进行比较

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
const int MOD=1000000007;
const int MN=1010;
int father[MN];
int num[MN][MN];
int rank[MN];
int f[MN][MN];
int val[MN],pi[MN];
int vis[MN];
int cnt[MN];
 
void Make_set(int n)
{
    for(int i=0; i<=n; i++)
    {
        father[i]=i;
    }
}
 
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
 
void Union(int x,int y)
{
    if(x==y) return ;
    father[x]=y;
}
 
int main()
{
    int i,j,k,n,m;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Make_set(n);
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&val[i],&pi[i]);
        }
        int a,b;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&a,&b);
            int x=Find(a);
            int y=Find(b);
            Union(x,y);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            int t=Find(i);
            vis[t]++;
        }
        int cas=0;
        for(i=1; i<=n; i++)
        {
            if(vis[i])
            {
                ++cas;
                int tes=0;
                for(j=1; j<=n; j++)
                {
                    if(father[j]==i)
                        num[cas][++tes]=j;
                }
                cnt[cas]=vis[i];
            }
        }
        memset(f,0,sizeof(f));
        for(i=1;i<=cas;i++)
        {
            for(j=m;j>=0;j--)
            {
                for(k=1;k<=cnt[i];k++)
                {
                    int xx=num[i][k];
                    if(j-pi[xx]>=0)
                    {
                        f[i][j]=max(f[i][j],f[i-1][j-pi[xx]]+val[xx]);
                        f[i][j]=max(f[i-1][j],f[i][j]);
                    }
                    else f[i][j]=max(f[i][j],f[i-1][j]);
                }
            }
        }
        printf("%d\n",f[cas][m]);
    }
    return 0;
}

分组背包：http://www.nocow.cn/index.php/%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2013-10-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法