题意：
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 }