題意：
n個(gè)節(jié)點(diǎn)組成一個(gè)環(huán)，相鄰節(jié)點(diǎn)間可以連邊，有m對(duì)點(diǎn)間需要通訊，問最少要構(gòu)造多少通訊線路
解答：
首先，要明確一點(diǎn)，a,b之間要通訊，只能有兩種通訊線路[1,a),[a,n)，還有一個(gè)重要條件就是最多只需要構(gòu)建n-1條邊能將所有點(diǎn)聯(lián)通。這樣就只要枚舉斷電點(diǎn)，所有對(duì)通訊節(jié)點(diǎn)中的連接方式就都確定了，因?yàn)檫B接路徑是互補(bǔ)的。斷開一個(gè)點(diǎn)，一條路徑就被砍斷了，只能選擇另外一條。然后統(tǒng)計(jì)覆蓋的點(diǎn)的時(shí)候建議使用樹狀數(shù)組，樹狀數(shù)組表示這種左開右閉的區(qū)間是很給力的。左端點(diǎn)+1，右端點(diǎn)-1，復(fù)雜度n2logn。
代碼
1 # include <cstdio>
2 # include <utility>
3 # include <functional>
4 # include <iostream>
5 # include <algorithm>
6 # include <cstring>
7 # define lowbit(a) (a&-a)
8 using namespace std;
9 int arr[1005],n,m;
10 pair<int,int>data[10005];
11 void add(int p,int num)
12 {
13 while(p<=n)
14 arr[p]+=num,p+=lowbit(p);
15 }
16 int sum(int p)
17 {
18 int res=0;
19 while(p>0)
20 res+=arr[p],p-=lowbit(p);
21 return res;
22 }
23 int main()
24 {
25 scanf("%d%d",&n,&m);
26 for(int i=0;i<m;i++)
27 {
28 scanf("%d%d",&data[i].first,&data[i].second);
29 if(data[i].first>data[i].second)
30 swap(data[i].first,data[i].second);
31 }
32 int ans=0xfffffff;
33 for(int i=1;i<=n;i++)
34 {
35 memset(arr,0,sizeof(arr));
36 for(int j=0;j<m;j++)
37 if(data[j].first<=i&&data[j].second>i)
38 add(1,1),add(data[j].first,-1),add(data[j].second,1);
39 else
40 add(data[j].first,1),add(data[j].second,-1);
41 int res=0;
42 for(int j=1;j<=n;j++)
43 if(sum(j)>0)
44 res++;
45 if(res<ans) ans=res;
46 }
47 printf("%d\n",ans);
48 return 0;
49 }