Skip to content

11283: 【原1283】Mixture

题目

题目描述

author: Cheezer 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1283

Description

CC非常喜欢化学,并且特别喜欢把一大堆液体倒在一起。

现在CC有n种液体,其中m对会发生反应,现在她想把这n种液体按某种顺序倒入一个容器内,让她获得最刺激的体验,使危险系数尽量大。

我们可以这样计算危险系数,一开始容器内没有任何液体,危险系数为1。每次液体倒入容器时,若容器内已有一种或多种液体会与这种液体发生反应,则危险系数会乘2,否则危险系数不变。

请你求出把这n种液体倒在一起的最大危险系数。

Input Format

第一行为两个数n和m。

接下来m行,每行两个数a, b。表示a号液体和b号液体会发生反应。保证同一种边不重复出现。

30%的数据: \( 1 \le n \le 10 \)

100%的数据: \( 1 \le n \le 1000 \)

Output Format

一行,即最大危险系数。

Sample Input

3 2
1 2
2 3

Sample Output

4

yyong119's solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int father[1050];
int num[350]={0};
int len = 1;
void mul2(int power){
    num[0]=1;
    for (int i = 0; i < power; ++i)
    {
        int r = 0;
        int ori_len = len;
        for (int j = 0; j < ori_len ; ++j)
        {
            int tmp = num[j]*2 + r;
            r = 0;
            num[j] = ( tmp ) % 10;
            if(tmp >= 10){
                r = (tmp)/10 ;
            }
        }
        if(r!=0)
            num[len++] = r;
    }
}

int find(int x) {

    if (x != father[x]) father[x] = find(father[x]);
    return father[x];
}

int main() {

    int n, m, k = 0;
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) father[i] = i;
    for (int i = 0; i < m; ++i) {
        int x,y; cin>>x>>y;
        int rootx = find(x) , rooty = find(y);
        if(rootx != rooty) father[rootx] = rooty;
    }
    for (int i = 1; i <= n; ++i) if(father[i]==i) k++;
    mul2(n-k);
    for (int i = len-1; i >=0; --i) cout<<num[i];
    return 0;
}