POJ 1944 - Fiber Communications

原题地址：http://poj.org/problem?id=1944

题目大意：有n个点排成一圈，可以连接任意两个相邻的点，给出 p 对点，要求这 p 对点必须直接或间接相连，求最少的连接边数

数据范围：n <= 1000, p <= 10000

算法分析：

一开始当最小生成树做的，才发现自己 SB 了……

先考虑不是环形而是线形的结构，直接贪心连接每两个点之间的所有点就好了。这样我们可以枚举环形的断点，然后逐次贪心，求最小解即可

很多同学在贪心的时候应用了线段树是复杂度高达O(np log n)，其实丝毫没有必要，我们只需要每次断点时生成一个数组，在每对点的左边点处加1，再在右边点处减1，然后求一下部分和，部分和中正数的个数即为所求（详见代码）

参考代码：

 //date 20140205

 #include <cstdio>

 #include <cstring>

 const int maxn = ;

 const int maxp = ;

 const int INF = 0x7F7F7F7F;

 inline void swap(int &a, int &b){int x = a; a = b; b = x;}

 inline int min(int a, int b){return a < b ? a : b;}

 int n, p;

 int pa[maxp][];

 int s[maxn << ];

 int main()

 {

     scanf("%d%d", &n, &p);

      for(int i = ; i <= p; ++i)

      {

          scanf("%d%d", &pa[i][], &pa[i][]);

         if(pa[i][] > pa[i][])swap(pa[i][], pa[i][]);

     }

     int ans = INF;

     for(int i = ; i <= n; ++i)

     {

         memset(s, , sizeof s);

         for(int j = ; j <= p; ++j)

         {

             int x = pa[j][], y = pa[j][];

             if(x <= i)x += n;

             if(y <= i)y += n;

             if(x > y)swap(x, y);

             ++s[x]; --s[y];

         }

         int now = , res = ;

         for(int j = ; j <= n; ++j)

         {

             now += s[i + j];

             if(now > )++res;

         }

         ans = min(ans, res);

     }

      printf("%d\n", ans);

     return ;

 }