049：Distance Statistics

Messj

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).

Messj

题目描述

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。

输出

符合要求的农场对数。

Messj

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'

#include<cstdio>
#include<cstring>
#include<algorithm> 

using namespace std;
const int maxn=40005;
int N,M,K;
int root;        //根结点 
int ans;        //结果 
int Max;        
struct node
{
        int v;
        int next;
        int w;
}edge[maxn*2];        //无向图 
int tot;        //结点总数total 
int head[maxn];        //头结点数组head 
int size[maxn];        //以v为根的子树节点数size 
int maxv[maxn];        
int vis[maxn];        //遍历标志visit 
int dis[maxn];        //距离数组distance 
int num;
void init()  
{  
    tot=0;  
    ans=0;  
    memset(head,-1,sizeof(head));  
    memset(vis,0,sizeof(vis));  
}   
//建立邻接表 
void add_edge(int u,int v,int w)
{
        edge[tot].v=v;
        edge[tot].w=w;
        edge[tot].next=head[u];//形成了链表，以-1结尾，以head为头结点，每个结点都是结点u的孩子。
        head[u]=tot++;
}
//计算子树所含节点数 
void dfssize(int u,int f) //除去f点外的规模，f一般为父结点 
{
        size[u]=1;        //本身 一个结点
        maxv[u]=0;        //其最大子树的结点数 
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
                int v=edge[i].v;
                if(v==f||vis[v])
                        continue;
                dfssize(v,u);
                size[u]+=size[v];
                if(size[v]>maxv[u])
                        maxv[u]=size[v];
        }
}
//确定树的重心，即最佳的根结点。
void dfsroot(int r,int u,int f)        //r为根结点，u为比较结点 
{
        if(size[r]-size[u]>maxv[u])        //size[r]-size[u]是u上面部分的树的尺寸，maxv[u]是u的最大子树的结点数。 
                maxv[u]=size[r]-size[u];//此处将树看作二叉树，把最大子树作为一枝，剩余的看作一枝 。将最大的一枝存入maxv中 
        if(maxv[u]<Max)        Max=maxv[u],root=u;  //MAX是maxv中最小值，由于maxv必不小于总结点的一半 ，故MAX存储的是当前最平衡结点的最大枝个数 
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
                int v=edge[i].v;
                if(v==f||vis[v])
                        continue;
                dfsroot(r,v,u);
        }
} 
//求每个点离重心的距离  
void dfsdis(int u,int d,int f)  
{
        dis[num++]=d;
        for(int i=head[u];i!=-1;i=edge[i].next)  
    {  
        int v=edge[i].v;  
        if(v!=f&&!vis[v])  
            dfsdis(v,d+edge[i].w,u);  
    }  
}
//计算以u为根的子树中有多少点对的距离小于等于K  
int calc(int u,int d)  //d为通向u的路径长度  
{  
    int ret=0;         //点对的个数 
    num=0;  //初始化 
    dfsdis(u,d,0);  
    sort(dis,dis+num);  
    int i=0,j=num-1;  //0点为根结点本身 
    while(i<j)  
    {  
        while(dis[i]+dis[j]>K&&i<j)j--;  
        ret+=j-i;  
        i++;  
    }  
    return ret;  
}  
void dfs(int u)
{
        Max=N;
        dfssize(u,0);
        dfsroot(u,u,0);        //设置u为根 
        ans+=calc(root,0);        //u树中的点对 
        vis[root]=1;        //根结点已遍历
        for(int i=head[root];i!=-1;i=edge[i].next)  
    {  
        int v=edge[i].v;  
        if(!vis[v])  
        {  
            ans-=calc(v,edge[i].w);  //删除掉同属于v结点且满足 dis[i]+dis[j]<K的点对。 
            dfs(v);  //加上以v为结点仅可过v结点满足 dis[i]+dis[j]<K的点对。
        }  
    }  
} 
int main()
{
        while(scanf("%d%d",&N,&M)!=EOF)
        {
                int u,v,w; 
                init();
                for(int i=1;i<=M;i++)  
        {  
                        char ch;
            scanf("%d%d%d %c",&u,&v,&w,&ch);  
            add_edge(u,v,w);  
            add_edge(v,u,w);  
        } 
        scanf("%d",&K);
                dfs(1);
                printf("%d\n",ans); 
        }
        return 0;
}