Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >CSU 1326: The contest(分组背包)

CSU 1326: The contest(分组背包)

作者头像
用户1624346
发布于 2018-04-17 08:25:14
发布于 2018-04-17 08:25:14
64500
代码可运行
举报
文章被收录于专栏:calmoundcalmound
运行总次数:0
代码可运行

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

题意:

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

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

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#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]进行比较

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
搜索专题
POJ  Best Sequence http://poj.org/problem?id=1699 题意:给你n个字符窜,求其所能拼接的最短长度。 分析:预处理下,dp[i][j]表示j接在i后头的最
用户1624346
2018/04/17
8410
POj 1797 Heavy Transportation
题意:求从1-n所能承受的最大重量是多少,其最大重量就是1-n通路的最小边 分析:求最大生成树的最小边,排序的时候按照权值从大到小派,然后生成树,知道找到1-n的通路就可以了 #include<stdio.h> #include<algorithm> using namespace std; const int MAXN=1005; const int INF=0x7fffffff; int father[MAXN]; int rank[MAXN]; int ans,n,m; struct Edge
用户1624346
2018/04/11
6510
动态规划集合
动态规划,少说也做了,30 40道了但是感觉还是没有入门,接下来一星期将重新做动态规划,hdu入门的,uva入门的,外加poj的,把动态规划都重新学一下 01背包知识点  1.Robberies (hdu2955)  (01背包变形) 第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱  最脑残的是把总的概率以为是抢N家银行的概率之和… 实际上可以将其转化为安全的概率,则两个概率相乘,就是两次抢劫的安全概率了。     正确的方程是:f[j]=max(dp[j],dp[j-
用户1624346
2018/04/17
1.1K0
强连通专题
求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int MN=1111; struct Edge { int to,next; }edge[MN<<2]; int dfn[MN]; int low[MN]; int head[MN<<2]; int subnet[MN]; int E,tp,ro
用户1624346
2018/04/17
6690
Is It A Tree?(并查集)
判断树是否唯一 1.只有一个根节点,(1)在一棵树上一个根节点。1 2 3 2就是两个根节点(1)只有一棵树 2.不成环,入度不大于1 由于数组运行超界导致wa,这是老毛病了 还一直错 #include<stdio.h> const int MAXN=1000100; int father[MAXN],rank[MAXN]; struct Node { int x,y; } node[MAXN]; void Make_set() { for(int i=1; i<MAXN; i++)
用户1624346
2018/04/11
7020
强连通专题
POJ 2762 Going from u to v or from v to u? 题意:判断该图的任意两点是否可达 分析:tarjan后进行缩点,缩点后再建图,判断该图是否为单链式图形(只有一个叶
用户1624346
2018/04/17
9780
How Many Tables (并查集)
题意:找几个不相连的团体,最后查找发现只要father有几个是自己的,就有几个团队,这个我没想到 #include<stdio.h> #include<string.h> const int MAXN=1010; int father[MAXN],rank[MAXN]; int hash[MAXN]; void Make_set(int n) { for(int i=0;i<=n;i++) { father[i]=i; rank[i]=0; } }
用户1624346
2018/04/11
6100
天梯赛 登顶题解
L 3-005 肿瘤诊断 题目链接: https://www.patest.cn/contests/gplt/L3-004 三维求连通块: 用并查集,或者广搜,如果用深搜的话会爆栈 #include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <math.h> using namespace std; int n
ShenduCC
2018/04/26
8010
「2017 Multi-University Training Contest 2」2017多校训练2
给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[j]-j。求a[n+1..2n]总和最大值。
饶文津
2020/06/02
3760
「2017 Multi-University Training Contest 2」2017多校训练2
poj----1330Nearest Common Ancestors(简单LCA)
题目连接  http://poj.org/problem?id=1330 就是构建一棵树,然后问你两个节点之间最近的公共父节点是谁? 代码: 1 /*Source Code 2 Problem:
Gxjun
2018/03/26
7260
Hand in Hand(并查集)
题意:判断两个图形是否相似,根据题意可以知道图形的分量,不是环就是链,所以我们只要依次两个图形是否一样就可以了 分析:若两个图形完全一样的话,那么它们成环和成链的个数必定一样,当然成环(链)的点的个数也是一样的,所以我们可以忽视结点的本身,          而值注重这个点代表的意义就可以。一样的两图排序后,自然会有对等的点和对等相同意义的点 #include<stdio.h> #include<algorithm> using namespace std; const int MAXN=10010; i
用户1624346
2018/04/17
6130
SDUT 2021 Winter Individual Contest – G
一辆车连司机可以坐5人,告诉你每个人开车从A到B或者从B到A花费的时间,一共有k辆车,问你让所有人从A到B花费的最少时间。车最终可以留在A地也可以留在B地,回程司机不能带人。
Here_SDUT
2022/08/08
3500
「2017 Multi-University Training Contest 1」2017多校训练1
1001 Add More Zero(签到题) 题目链接 HDU6033 Add More Zero image.png #include <cstdio> #include <cmath> int cas,m; int main(){ while(~scanf("%d",&m)){ printf("Case #%d: %d\n",++cas,(int)(m*log(2)/log(10))); } return 0; } 1002 Balala Power!(贪心) 题目链接 HDU6034 Ba
饶文津
2020/06/02
3900
「2017 Multi-University Training Contest 1」2017多校训练1
天梯赛模拟训练【3】
思路:一个从前往后遍历,一个从后往前,要设置一个flag,表示当前这个人是否匹配成功,当都匹配成功后就break。
杨鹏伟
2020/11/12
5910
Farm Irrigation
题意:判断图中的图形有几个集合。         这道题做的郁闷死我了,为了找开始字母的错误一个一个匹对。         这道题让我也懂得了表格的位置可以代表并查集的点,这样每个都不一样,而我想的那种用字母是否本身来判断有多少个集合是错误的,很明显一个字母不会只出现一次。而且在计算位置的时候也出错了,应该i*列代表的第几行 #include<stdio.h> #include<string.h> const int MAXN=110; int total; int gra_row[MAXN][MAXN],
用户1624346
2018/04/17
4600
搜索(DFS BFS)专题练习
题意:很简单的问题,就是一个地图,上面S是入口,然后E是出口。#代表陷阱不能走,问我们是否能够走出迷宫。
杨鹏伟
2020/09/10
4660
SDUT 2021 Winter Team Contest – 1
本题定义加法为不进位加法,如 3 + 8 = 1 3 + 8 = 13+8=1,乘法按竖式乘法计算,不进位。给定n(1 \leq n \leq 10^{25}),求满足 a ∗ a = n 的最小的 a,无解输出 − 1。
Here_SDUT
2022/08/08
4430
DSU_Exercise
dbq。 Template //非路径压缩 int find_1(int x) { int r = x; while(pre[r]!=r) { r = pre[r]; } return r; } //路径压缩 int find(int x) { if(pre[x]==x) return x; else { return pre[x] = find(pre[x]); } } void jo
AngelNH
2020/04/16
2960
UESTC 485 Game(康托展开,bfs打表)
Game Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status title Today I want to introduce an interesting game to you. Like eight puzzle, it is a square board with 99 positions, but it filled by 99 numbered
ShenduCC
2018/04/26
6450
ACM校赛网络赛部分题解
这次网络赛我共出了三题,现给出题解 自动售货机 由于测试样例很多,每次都计算会超时,所以要打表,递推方程为dp[i][j]=dp[i-1][j]+dp[i-1][j-1];注意优化剪枝,在dp循环过程中如果不剪枝,实打实的2000*1000也是会超时的。 #include<iostream> #include<cstdio> #include<cstdlib> #include<string.h> #include<math.h> #include<algorithm> #include<map> #i
triplebee
2018/01/12
6730
相关推荐
搜索专题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验