专栏首页calmoundCSU 1326: The contest(分组背包)

CSU 1326: The contest(分组背包)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • zoj 2521 LED Display

    题意:开灯,每个数字都由好几个灯组成,其中一些数字灭掉某些灯可以成为另一个数字,如0灭掉3个灯可以变成7,         现给你一组数字,如何组合可以形成最少...

    用户1624346
  • HDU 1863 畅通工程

    一道很朴素的最小生成树,不过通过此题知道了,当n已经决定的情况下,若n个点无法构成最小生成树的话,最终得到ans无法得到精确的值,他会将无穷大的路径加入。 #i...

    用户1624346
  • 搜索专题

    POJ  Best Sequence http://poj.org/problem?id=1699 题意:给你n个字符窜,求其所能拼接的最短长度。 分析:预处理...

    用户1624346
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 【C语言笔记】函数参数压栈的顺序?

    按照日常习惯来看,C语言的函数参数压栈顺序是从左到右吧?但是事实却是相反的,C语言函数参数压栈顺序是从右到左的。下面看一个程序:

    正念君
  • 图论--拓扑排序--模板

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券