程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 5971 打擊犯罪,深圳打擊證券犯罪

5971 打擊犯罪,深圳打擊證券犯罪

編輯:C++入門知識

5971 打擊犯罪,深圳打擊證券犯罪


題目描述 Description

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

輸入描述 Input Description

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

輸出描述 Output Description

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

樣例輸入 Sample Input

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

樣例輸出 Sample Output

1

 輸出1(打擊掉紅色團伙

數據范圍及提示 Data Size & Hint

n<=1000

 

思路:逆向+分治

   這樣退出來的一定是最小值

   具體為什麼自己代入一組數據看看就全明白了

   非語言能形容

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 struct node
 6 {
 7     int u;
 8     int v;
 9     int w;
10     int next;
11 }edge[10001];
12 int head[1001];
13 int num=1;
14 int map[1001][1001];
15 int vis[10001];
16 int tot;//記錄每次搜索時所能搜索到的點的數量 
17 int n;
18 void add(int x,int y)
19 {
20     map[x][y]=1;
21     map[y][x]=1;
22 }
23 void dfs(int x)
24 {
25     vis[x]=1;
26     tot++;
27     for(int i=1;i<=n;i++)
28     {
29         if(map[x][i]==1&&vis[i]==0)
30         {
31             dfs(i);
32         }
33     }
34 }
35 
36 int main()
37 {
38 
39     scanf("%d",&n);
40     for(int i=1;i<=n;i++)
41     head[i]=-1;
42     for(int i=1;i<=n;i++)
43     {
44         int m;
45         scanf("%d",&m);
46         for(int j=1;j<=m;j++)
47         {
48             int p;
49             scanf("%d",&p);
50             edge[num].u=i;
51             edge[num].v=p;
52             //edge[num].w=p;
53             edge[num].next=head[i];
54             head[i]=num++;
55         }
56     }
57     /*for(int i=1;i<=n;i++)
58     {
59         int j=head[i];
60         while(j!=-1)
61         {
62             cout<<edge[j].v<<" ";
63             j=edge[j].next;
64         }
65         cout<<endl;
66     }
67     cout<<"********************************"<<endl;
68     for(int i=1;i<=n;i++)
69     {
70         cout<<edge[head[i]].v<<endl;
71     }*/
72     for(int i=n;i>=1;i--)
73     {
74         int j=head[i];
75         while(j!=-1)
76         {
77             if(edge[j].v>=i)
78             {
79                 add(edge[j].v,i);
80                 tot=0;
81                 memset(vis,0,sizeof(vis));
82                 dfs(i);
83                 if(tot>n/2)
84                 {
85                     cout<<i;
86                     return 0;
87                 }
88             }
89             j=edge[j].next;
90         }
91     }
92     cout<<-1;
93     return 0;
94 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved