打擊犯罪

ssl 2342

題目大意：

有n個人某些人之間有連接（連接成一個團伙），現在要最大的團伙人數不大于n/2，要最少要刪掉幾個人（要按順序刪）

原題：

題目描述：

某個地區有n(n<=1000)個犯罪團伙，當地警方按照他們的危險程度由高到低給他們編號為1-n，他們有些團伙之間有直接聯系，但是任意兩個團伙都可以通過直接或間接的方式聯系，這樣這里就形成了一個龐大的犯罪集團，犯罪集團的危險程度唯一由集團內的犯罪團伙數量確定，而與單個犯罪團伙的危險程度無關（該犯罪集團的危險程度為n）。現在當地警方希望花盡量少的時間（即打擊掉盡量少的團伙），使得龐大的犯罪集團分離成若干個較小的集團，并且他們中最大的一個的危險程度不超過n/2。為達到最好的效果，他們將按順序打擊掉編號1到k的犯罪團伙，請編程求出k的最小值。

輸入

第一行一個正整數n
接下來的n行每行有若干個正整數，第一個整數表示該行除第一個外還有多少個整數，若第i行存在正整數k，表示i,k兩個團伙可以直接聯系

輸出

一個正整數，為k的最小值

輸入樣例

7 2 2 5 3 1 3 4 2 2 4 2 2 3 3 1 6 7 2 5 7 2 5 6

輸出樣例

1

解題思路：

因為是按順序打擊的，所以倒著循環，每次添加一個人，如果沒超過那繼續，如果超過了就直接輸出

代碼：

#include<cstdio> using namespace std; int n,x,y,pp,p[1005],dad[1005],s[1005],b[1005][1005]; int find(int dep){return dad[dep]==dep?dep:dad[dep]=find(dad[dep]);} //并查集 int main() {scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%d",&b[i][0]);for (int j=1;j<=b[i][0];++j)scanf("%d",&b[i][j]);s[i]=1;//預處理dad[i]=i;}for (int i=n;i>0;--i){p[i]=1;for (int j=1;j<=b[i][0];++j)//合并其他的if (find(i)!=find(b[i][j])&&p[b[i][j]]){x=find(i);y=find(b[i][j]);if (x>y){dad[y]=x;s[x]+=s[y]; //累加}else{dad[x]=y;s[y]+=s[x];}}for (int j=i;j<=n;++j)if (s[j]>n/2)//判斷符不符合{printf("%d",i);pp=1;break;}if (pp) break;} }

總結

以上是生活随笔為你收集整理的【并查集】打击犯罪（ssl 2342）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。