小 X 的液體混合
雖然小 X 不喜歡化學原理，但他特別喜歡把一大堆液體倒在一起，
現在小 X 有 n 種液體，其中 m 對會發生反應，現在他想把這 n 種液體按某種順序倒入一個容器
內，讓他獲得最刺激的體驗，也就是使危險系數盡量大，
我們可以這樣計算危險系數，一開始容器內沒有任何液體，危險系數為 1，每次液體倒入容器時，
若容器內已有一種或多種液體會與這種液體發生反應，則危險系數會乘 2，否則危險系數不變，
最大危險系數小 X 不會算，希望你幫幫他，
Input
第一行包含兩個整數 n, m，
接下來 m 行，每行包含兩個整數 a, b，表示液體 a 和液體 b 會發生反應，
Output
第一行包含一個整數，表示最大危險系數，
思路
首先我們可以知道：
每
一
個
連
通
塊
一
定
有
一
個
液
體
倒
入
時
無
法
增
加
危
險
系
數
每一個連通塊一定有一個液體倒入時無法增加危險系數
每一個連通塊一定有一個液體倒入時無法增加危險系數
證明：
在每一個連通塊中，連通的邊都是雙向的，而且每2個點之間都能相連（這不是廢話嗎），所以我們可以刪去一部分不必要的邊，組成一顆樹，而這顆樹的根在進入瓶子時是無法增加危險系數的，而當根進入后，讓它的子節點進入都可以增加，再讓子節點的子節點進去，讓子節點的子節點進入……
那么如何統計連通塊的個數呢？
由于每2個點之間都能相連，所以我們可以讓任何一個點做根，用并查集統計就可以了
記住之后累乘寫高精
code：
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
bool a[1001][1001];
int f[1001];
char x2[100001];
string chen(string x)
{
for (int i=x.size()-1,j=1;i>=0;i--,j++) x2[j]=x[i]-'0';
int p=0;
for (int i=1;i<=x.size();i++)
{
int t=x2[i]*2+p;
p=t/10;
x2[i]=t%10;
}
x2[x.size()+1]=p;
string s="";
int i=100000;
while (i>1&&x2[i]==0) i--;
while (i>=1)
{
char xx=x2[i]+'0';
s+=xx;
i--;
}
return s;
}//高精度乘法（乘2）
int find(int x)
{
if (x==f[x]) return x;
return f[x]=find(f[x]);
}//并查集路徑壓縮
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
f[find(y)]=find(x);
}
string s="";
char x='1';
s+=x;
int tot=n;
for (int i=1;i<=n;i++)
{
if (find(i)==i) tot--;
}//求連通塊個數（根的個數）
for (int i=1;i<=tot;i++)
{
s=chen(s);
}
for (int i=0;i<s.size();i++)
{
int u=s[i];
cout<<u-'0';
}return 0;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/176153.html
標籤：其他
上一篇：Python實作坦克大戰
下一篇：Unity 操作快捷鍵（全）