【題目描述】

某個(gè)地區(qū)有n(n≤1000)個(gè)犯罪團(tuán)伙，當(dāng)?shù)鼐桨凑账麄兊奈ｋU(xiǎn)程度由高到低給他們編號(hào)為1-n，他們有些團(tuán)伙之間有直接聯(lián)系，但是任意兩個(gè)團(tuán)伙都可以通過(guò)直接或間接的方式聯(lián)系，這樣這里就形成了一個(gè)龐大的犯罪集團(tuán)，犯罪集團(tuán)的危險(xiǎn)程度由集團(tuán)內(nèi)的犯罪團(tuán)伙數(shù)量唯一確定，而與單個(gè)犯罪團(tuán)伙的危險(xiǎn)程度無(wú)關(guān)（該犯罪集團(tuán)的危險(xiǎn)程度為n）。現(xiàn)在當(dāng)?shù)鼐较ＭūM量少的時(shí)間（即打擊掉盡量少的團(tuán)伙），使得龐大的犯罪集團(tuán)分離成若干個(gè)較小的集團(tuán)，并且他們中最大的一個(gè)的危險(xiǎn)程度不超過(guò)n/2。為達(dá)到最好的效果，他們將按順序打擊掉編號(hào)1到k的犯罪團(tuán)伙，請(qǐng)編程求出k的最小值。

【輸入】

第一行一個(gè)正整數(shù)n。接下來(lái)的n行每行有若干個(gè)正整數(shù)，第一個(gè)整數(shù)表示該行除第一個(gè)外還有多少個(gè)整數(shù)，若第i行存在正整數(shù)k，表示i，k兩個(gè)團(tuán)伙可以直接聯(lián)系。

【輸出】

一個(gè)正整數(shù)，為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<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 123 #define E 1e-6 using namespace std; struct node{int pre;int next; }a[N*N]; int father[N]; int head[N],ans[N]; int cnt; void add(int x,int y) {cnt++;a[cnt].pre=y;a[cnt].next=head[x];head[x]=cnt;cnt++;a[cnt].pre=x;a[cnt].next=head[y];head[y]=cnt; } int Find(int x) {if(father[x]==x)return x;return father[x]=Find(father[x]); } int main() {int n;cin>>n;for(int i=1;i<=n;i++){father[i]=i;ans[i]=1;int m;cin>>m;for(int j=1;j<=m;j++){int k;cin>>k;add(i,k);}}for(int i=n;i>=1;i--){int x=Find(i);int k=head[i];while(k!=0){int j=a[k].pre;if(j>i){int y=Find(j);if(x!=y){father[y]=x;ans[x]+=ans[y];if(ans[x]>n/2){cout<<i<<endl;return 0;}}}k=a[k].next;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的打击犯罪（信息学奥赛一本通-T1386）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。