首页 > 代码库 > zoj2913BFS

zoj2913BFS

2024-07-15 07:59:37   214人阅读

题意：其实看图很好理解题目意思，就是在图中找一个点，使到所有的目标地点的最大距离最小。

思路：一看这题就觉得是BFS，因为可以很好的广搜，但是枚举任意一点搜索会T，因为最多有10000个点。我们既然可以从一个点到每个目标点的距离求得，为何不可枚举每个目标点，到一个点的距离的最大值，使之最小的点应该就是索要找的点了；

 

以上图的地区布图为例加以解释，我们可以求得每个点的最大star值，start[7400] ~ star[7416] 的取值分别为：4、4、4、4、4、5、4、5、5、5、5、5、4、5、5、5、5.明显题目是有多解的，题目要求取最小值。

代码：

#include<cstdio>#include<cstring>#include<queue>#include<vector>const int maxn = 10009;inline int max(int a,int b) {return a > b ? a : b;}struct NODE{    int v,next;}eg[maxn*10];int head[maxn];struct node{    int v,step;    node(int a,int b):v(a),step(b){}};int vis[maxn];int route[20][30];int star[maxn];int n,tot;//std::vector<int> vec[maxn];void add(int a,int b){    eg[tot].v = b;    eg[tot].next = head[a];    head[a] = tot++;}void BFS(int s){    memset(vis,0,sizeof(vis));    std::queue<node> q;    q.push(node(s,1));    star[s] = max(star[s],1);    vis[s] = 1;    while(!q.empty())    {        int u = q.front().v;        int step = q.front().step;        q.pop();        for(int i=head[u];i+1;i=eg[i].next)        {            int v =eg[i].v;            if(vis[v])continue;            vis[v] = 1;            star[v] = max(star[v],step+1);            q.push(node(v,step+1));        }    }}void init(){    memset(star,0,sizeof(star));    memset(vis,0,sizeof(vis));    memset(head,-1,sizeof(head));    memset(route,-1,sizeof(star));    tot = 0;}int main(){    int t,m,a,b,c,i,j;    scanf("%d",&t);    while(t--)    {        init();        scanf("%d%d",&n,&m);        int ma = 0;        for(i=0;i<n;i++)        {            scanf("%d%d",&a,&c);            while(c--)            {                scanf("%d",&b);                add(a,b);                ma = max(ma,b);                ma = max(ma,a);            }        }        for(i=0;i<m;i++)        {            scanf("%d",&a);            for(j=0;j<a;j++)            {                scanf("%d",&route[i][j]);                BFS(route[i][j]);            }        }    //    BFS(route[0][0]);        int ans = maxn;        int id;        for(i=0;i<=ma;i++)        {            if(star[i] == 0)continue;    //        printf("%d %d\n",i,star[i]);            if(star[i] < ans)            {                ans = star[i];                id = i;            }        }        printf("%d %d\n",ans,id);    }    return 0;}/*117 27400 6 7401 7402 7403 7404 7405 74067401 6 7412 7402 7400 7406 7410 74117402 5 7412 7403 7400 7401 74117403 6 7413 7414 7404 7400 7402 74127404 5 7403 7414 7415 7405 74007405 6 7404 7415 7407 7408 7406 74007406 7 7400 7405 7407 7408 7409 7410 74017407 4 7408 7406 7405 74157408 4 7409 7406 7405 74077409 3 7410 7406 74087410 4 7411 7401 7406 74097411 5 7416 7412 7402 7401 74107412 6 7416 7411 7401 7402 7403 74137413 3 7412 7403 74147414 3 7413 7403 74047415 3 7404 7405 74077416 2 7411 74125 7409 7408 7407 7405 74156 7415 7404 7414 7413 7412 7416  */

 


联系
我们