pku1944 Fiber Communications 图论好题!总体上的观察,算法不难

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

posted on 2011-02-05 01:20 yzhw 阅读(220) 评论(0)  编辑 收藏 引用 所属分类: graphdata struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年2月>
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜