b839 - 104北二3.朋友
題目描述
題目要求找出在一群人中，朋友關係所構成的最大團體人數。朋友關係的定義是：如果兩個人的名字相似（最長共同子序列長度不小於名字長度的 1/2），或者他們有共同朋友，則他們是朋友。
解題思路
本題的核心思路是使用 Union-Find (並查集) 演算法來維護朋友關係，並使用動態規劃 (Dynamic Programming) 計算兩個名字的相似度。
- 計算名字相似度： 對於每對名字，使用動態規劃計算它們的最長共同子序列 (LCS) 的長度。如果 LCS 的長度大於或等於兩個名字長度的最小值的一半，則認為這兩個名字相似，並將它們合併到同一個集合中。
- 維護朋友關係： 使用 Union-Find 演算法來維護朋友關係。如果兩個人的名字相似，或者他們屬於同一個集合，則將它們合併到同一個集合中。
- 找出最大團體： 遍歷所有集合，找出包含人數最多的集合，其人數即為最大團體的人數。
複雜度分析
- 時間複雜度: O(N^2 * L^2 + N * α(N))，其中 N 是人的數量，L 是名字的最大長度，α(N) 是反阿克曼函數，在實際應用中可以視為常數。N^2 * L^2 是計算所有名字對的 LCS 的時間複雜度，N * α(N) 是 Union-Find 演算法的時間複雜度。
- 空間複雜度: O(N + L^2)，其中 N 是人的數量，L 是名字的最大長度。O(N) 是 Union-Find 演算法所需的空間，O(L^2) 是動態規劃計算 LCS 時所需的空間。
程式碼
#include <bits/stdc++.h>
using namespace std;
int t,n,fa[50],p[50],dp[55][55],ma;
string s[50];
int ff(int x){
if(fa[x]==x)return x;
return fa[x]=ff(fa[x]);
}
void mg(int x,int y){
x=ff(x);
y=ff(y);
if(x==y)return;
if(p[x]<p[y])swap(x,y);
fa[y]=x;
p[x]+=p[y];
ma=max(ma,p[x]);
p[y]=0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n;
ma=1;
for(int i=0;i<n;++i){
fa[i]=i;
p[i]=1;
cin >> s[i];
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(ff(i)==ff(j))continue;
memset(dp,0,sizeof(dp));
int m1=s[i].size(),m2=s[j].size();
for(int ii=0;ii<m1;++ii){
for(int jj=0;jj<m2;++jj){
if(s[i][ii]==s[j][jj]){
dp[ii+1][jj+1]=dp[ii][jj]+1;
}
else{
dp[ii+1][jj+1]=max(dp[ii][jj+1],dp[ii+1][jj]);
}
}
}
if(dp[m1][m2]*2>=min(m1,m2)){
mg(i,j);
}
}
}
cout << ma << "\n";
}
}