題意：
n個節點組成一個環，相鄰節點間可以連邊，有m對點間需要通訊，問最少要構造多少通訊線路
解答：
首先，要明確一點，a,b之間要通訊，只能有兩種通訊線路[1,a),[a,n)，還有一個重要條件就是最多只需要構建n-1條邊能將所有點聯通。這樣就只要枚舉斷電點，所有對通訊節點中的連接方式就都確定了，因為連接路徑是互補的。斷開一個點，一條路徑就被砍斷了，只能選擇另外一條。然后統計覆蓋的點的時候建議使用樹狀數組，樹狀數組表示這種左開右閉的區間是很給力的。左端點+1，右端點-1，復雜度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 }