鱼C论坛

 找回密码
 立即注册
查看: 2332|回复: 2

[技术交流] 049:Distance Statistics

[复制链接]
发表于 2018-2-18 22:07:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Description

Frustrated at the number of distance queries required to find a reasonable route for his cow marathon, FJ decides to ask queries from which he can learn more information. Specifically, he supplies an integer K (1 <= K <= 1,000,000,000) and wants to know how many pairs of farms lie at a distance at most K from each other (distance is measured in terms of the length of road required to travel from one farm to another). Please only count pairs of distinct farms (i.e. do not count pairs such as (farm #5, farm #5) in your answer).
Input

* Lines 1 ..M+1: Same input format as in "Navigation Nightmare"

* Line M+2: A single integer, K.
Output

* Line 1: The number of pairs of farms that are at a distance of at most K from each-other.
Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
Sample Output

5
Hint

There are 5 roads with length smaller or equal than 10, namely 1-4 (3), 4-7 (2), 1-7 (5), 3-5 (7) and 3-6 (9).

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-2-18 22:08:05 | 显示全部楼层
题目描述

Farmer John现在给出一个整数K (1 <= K <= 1,000,000,000),要求你计算出相隔路程不超过K的农场的对数。
(Tips:1>被计算的农场必须是不同的两个农场;2>农场之间的路程由道路的长度决定)

输入

第1行:包含两个整数N (2 <= N <= 40,000)和M (1 <= M < 40,000)。N表示农场数,M表示道路数。
第2~M+1行:每一行给出一条道路的信息F1、F2(连接的两个农场)、L(道路长度,1 <= L <= 1000)、D(从F1到F2的方向,用N、S、W、E表示,在本题中没有作用)
第M+2行:一个整数K。

输出

符合要求的农场对数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-2-19 02:01:54 | 显示全部楼层
scanf("%d %c %c",&a, &b , &c);输入语句中加的有空格。如果不加空格写成scanf("%d%c%c",&a, &b, &c);而用键盘输入“3空e空f”时会出错的。

在不加空格的情况下"%d%c%c",&a, &b , &c 当你输入“3空e空f”  你第一个是整形 自然会把你输入的数字给第一个a,你输入第二个是空格,会把这个空格当成字符赋值给b 你输入第三个是e,会把e赋值给c 这样程序就认为已经完成了赋值,而不会理会后面的"空f"
结果a=3,b=' ',c='e'


  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>

  4. using namespace std;
  5. const int maxn=40005;
  6. int N,M,K;
  7. int root;        //根结点
  8. int ans;        //结果
  9. int Max;       
  10. struct node
  11. {
  12.         int v;
  13.         int next;
  14.         int w;
  15. }edge[maxn*2];        //无向图
  16. int tot;        //结点总数total
  17. int head[maxn];        //头结点数组head
  18. int size[maxn];        //以v为根的子树节点数size
  19. int maxv[maxn];       
  20. int vis[maxn];        //遍历标志visit
  21. int dis[maxn];        //距离数组distance
  22. int num;
  23. void init()  
  24. {  
  25.     tot=0;  
  26.     ans=0;  
  27.     memset(head,-1,sizeof(head));  
  28.     memset(vis,0,sizeof(vis));  
  29. }   
  30. //建立邻接表
  31. void add_edge(int u,int v,int w)
  32. {
  33.         edge[tot].v=v;
  34.         edge[tot].w=w;
  35.         edge[tot].next=head[u];//形成了链表,以-1结尾,以head为头结点,每个结点都是结点u的孩子。
  36.         head[u]=tot++;
  37. }
  38. //计算子树所含节点数
  39. void dfssize(int u,int f) //除去f点外的规模,f一般为父结点
  40. {
  41.         size[u]=1;        //本身 一个结点
  42.         maxv[u]=0;        //其最大子树的结点数
  43.         for(int i=head[u];i!=-1;i=edge[i].next)
  44.         {
  45.                 int v=edge[i].v;
  46.                 if(v==f||vis[v])
  47.                         continue;
  48.                 dfssize(v,u);
  49.                 size[u]+=size[v];
  50.                 if(size[v]>maxv[u])
  51.                         maxv[u]=size[v];
  52.         }
  53. }
  54. //确定树的重心,即最佳的根结点。
  55. void dfsroot(int r,int u,int f)        //r为根结点,u为比较结点
  56. {
  57.         if(size[r]-size[u]>maxv[u])        //size[r]-size[u]是u上面部分的树的尺寸,maxv[u]是u的最大子树的结点数。
  58.                 maxv[u]=size[r]-size[u];//此处将树看作二叉树,把最大子树作为一枝,剩余的看作一枝 。将最大的一枝存入maxv中
  59.         if(maxv[u]<Max)        Max=maxv[u],root=u;  //MAX是maxv中最小值,由于maxv必不小于总结点的一半 ,故MAX存储的是当前最平衡结点的最大枝个数
  60.         for(int i=head[u];i!=-1;i=edge[i].next)
  61.         {
  62.                 int v=edge[i].v;
  63.                 if(v==f||vis[v])
  64.                         continue;
  65.                 dfsroot(r,v,u);
  66.         }
  67. }
  68. //求每个点离重心的距离  
  69. void dfsdis(int u,int d,int f)  
  70. {
  71.         dis[num++]=d;
  72.         for(int i=head[u];i!=-1;i=edge[i].next)  
  73.     {  
  74.         int v=edge[i].v;  
  75.         if(v!=f&&!vis[v])  
  76.             dfsdis(v,d+edge[i].w,u);  
  77.     }  
  78. }
  79. //计算以u为根的子树中有多少点对的距离小于等于K  
  80. int calc(int u,int d)  //d为通向u的路径长度  
  81. {  
  82.     int ret=0;         //点对的个数
  83.     num=0;  //初始化
  84.     dfsdis(u,d,0);  
  85.     sort(dis,dis+num);  
  86.     int i=0,j=num-1;  //0点为根结点本身
  87.     while(i<j)  
  88.     {  
  89.         while(dis[i]+dis[j]>K&&i<j)j--;  
  90.         ret+=j-i;  
  91.         i++;  
  92.     }  
  93.     return ret;  
  94. }  
  95. void dfs(int u)
  96. {
  97.         Max=N;
  98.         dfssize(u,0);
  99.         dfsroot(u,u,0);        //设置u为根
  100.         ans+=calc(root,0);        //u树中的点对
  101.         vis[root]=1;        //根结点已遍历
  102.         for(int i=head[root];i!=-1;i=edge[i].next)  
  103.     {  
  104.         int v=edge[i].v;  
  105.         if(!vis[v])  
  106.         {  
  107.             ans-=calc(v,edge[i].w);  //删除掉同属于v结点且满足 dis[i]+dis[j]<K的点对。
  108.             dfs(v);  //加上以v为结点仅可过v结点满足 dis[i]+dis[j]<K的点对。
  109.         }  
  110.     }  
  111. }
  112. int main()
  113. {
  114.         while(scanf("%d%d",&N,&M)!=EOF)
  115.         {
  116.                 int u,v,w;
  117.                 init();
  118.                 for(int i=1;i<=M;i++)  
  119.         {  
  120.                         char ch;
  121.             scanf("%d%d%d %c",&u,&v,&w,&ch);  
  122.             add_edge(u,v,w);  
  123.             add_edge(v,u,w);  
  124.         }
  125.         scanf("%d",&K);
  126.                 dfs(1);
  127.                 printf("%d\n",ans);
  128.         }
  129.         return 0;
  130. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 06:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表