牛客算法竞赛入门课第四节习题

经商：并查集加01背包

https://ac.nowcoder.com/acm/problem/14545

思路：先用并查集找出与编号1可以交际的人重新存放到数组中，然后用01背包找出最大利益值，这里要采用滚动数组，不然会内存超限。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 1e6+5;
#define LL long long
const int inx = INT_MAX; 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 

int a[10005],b[10005],dp[10005],p[10005],t;
int find_set(int x)
{
    if(x != p[x]) p[x] = find_set(p[x]);
    return p[x];
}

void union_set(int x,int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x != y) p[x] = p[y];
}

int main()
{
    int T,N,M,c,i,j,x,y;
    cin >> T;
    while(T--){
        t = 0;
        cin >> N >> M >> c;
        for(i = 1; i <= N; i++) p[i] = i;
        for(i = 2; i <= N; i++){
            cin >> a[i] >> b[i];
        }
        for(i = 0; i < M; i++){
            cin >> x >> y;
            union_set(x,y);
}
        x = find_set(1);
        for(i = 2; i <= N; i++){
            y = find_set(i);
            if(x == y){
                a[t] = a[i];
                b[t++] = b[i];
            }
        }
    memset(dp,0,sizeof(dp));
    for(i = 0; i < t; i++){
        for(j = c; j >= a[i]; j--){
            dp[j] = max(dp[j],dp[j - a[i]] + b[i]);
        }
    }
    cout << dp[c] << endl;
}
}

A Bug's Life（种类性并查集）

https://ac.nowcoder.com/acm/problem/107089

思路：
1：题目大致的意思就是给你一个昆虫两两交互的列表，而两个昆虫能够交互只能时一公一母，否则这个列表存在问题，那么也就是判断这个列表里面有没有哪对昆虫给的是错误信息。
2：很明显的并查集，对于每个昆虫，它有公或母两种可能，分情况讨论，比如1，3，那么1(0)-3(1),1(1)-3(0),括号里面0表示公，1表示母，这样就形成了两条链连起来。
3：实际操作时假设有n个昆虫，一个编号有i的昆虫，它为公时是i，为母时是i+n，就这样可以形成两条链。
4：我们可以先假设第一对是真的，然后去判断后面每对的真假性，只要有错就可以跳出循环输出。

//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#define LL long long
#define inf 0x3f
const int mod = 1e9+7;
using namespace std;

int a[4010];
int find(int x){
    if(x != a[x]) a[x] = find(a[x]);
    return a[x];
}

void merge(int x,int y){
    x = find(x);
    y = find(y);
    if(x != y) a[x] = a[y];
}

int main()
{
    int t,temp,m,n,x,y;
    scanf("%d",&t);
    for(int i = 1; i <= t; i++){
        temp = 0;
        scanf("%d%d",&n,&m);
        for(int j = 1; j <= n*2; j++) a[j] = j;
        while(m--){
            scanf("%d%d",&x,&y);
            if(find(x) == find(y) || find(x+n) == find(y+n)){//判断真假
                temp++;
                break;
            }
            merge(x,y+n);//x为公，y为母。
            merge(x+n,y);//x为母，y为公。
        }
        if(i != 1) printf("\n");
            if(!temp){
            printf("Scenario #%d:\n",i);
            printf("No suspicious bugs found!\n");
        }
        else{
            printf("Scenario #%d:\n",i);
            printf("Suspicious bugs found!\n");
        }
    }
    return 0;
}

建筑抢修：优先队列+贪心（给贪心一个反悔的机会）

https://ac.nowcoder.com/acm/problem/20154

思路：这道题首先会想的是按限制时间由小到大排列，判断这个建筑的修建时间加上前面几个建筑的修建时间是否小于这个建筑的限制时间，如果小于，则修建，让建筑时间入队，否则的话判断对顶元素是否大于这个建筑的修建时间，如果大于则出队，并让总时间减去对顶元素的大小，但建筑个数不变。