[CF] 986 A. Fair

[CF] 986 A. Fair

大家好,又见面了,我是你们的朋友全栈君。

http://codeforces.com/problemset/problem/986/A

n个点的无向连通图,每个点有一个属性,求每个点到s个不同属性点的最短距离

 

依稀记得那天晚上我和Menteur-Hxy探讨这道题如何不可做的样子

直观想法当然是每个点出发bfs,找到s个就停止,但这最差是n^2的,不能接受!

解法是多源广搜,注意到货物种类非常小(<=100),所以可以求出每个点获得每种货物的最短距离。

做法是进行k次bfs,对于第i次,起点st是每个种类为i的点,广搜的性质决定了她们的平行关系。

这样就可以求出每种货物到每个点的距离,换言之,就是每个点获得每种货物的代价(最小)

然后对于每个点,答案就是最小的s个啦

 

无向图注意开两倍边

 

 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int MAXN=100005;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}

struct Edge{
  int next,to;
}e[MAXN<<1];
int ecnt,head[MAXN];
inline void add(int x,int y){
  e[++ecnt].to = y;
  e[ecnt].next = head[x];
  head[x] = ecnt;
}

int dis[MAXN][102],typ[MAXN];
//dis[i][j] - the minimum cost for town i to get the j-th goods

int n,m,k,s;

queue<int> Q;
void bfs(int x){
  for(int i=1;i<=n;i++) if(typ[i]==x) Q.push(i),dis[i][x]=0;
  while(!Q.empty()){
    int top=Q.front();Q.pop();
    for(int i=head[top];i;i=e[i].next){
      int v=e[i].to;
      if(dis[v][x]>dis[top][x]+1){
          dis[v][x]=dis[top][x]+1;
          Q.push(v);
      }
    }
  }
}

void init(){
  memset(dis,0x3f,sizeof(dis));
}

vector<int> V;

int main(){
  n=rd();m=rd();k=rd();s=rd();
  init();
  for(int i=1;i<=n;i++) typ[i]=rd();
  int x,y,w;
  for(int i=1;i<=m;i++){
    x=rd();y=rd();
    add(x,y);add(y,x);
  }
  for(int i=1;i<=k;i++) bfs(i);
  int ret=0;
  for(int i=1;i<=n;i++){
    V.clear();
    for(int j=1;j<=k;j++) V.push_back(dis[i][j]);
    sort(V.begin(),V.end());
    ret=0;
    for(int j=0;j<s;j++) ret+=V[j];
    printf("%d ",ret);
  }
  return 0;
}

 

转载于:https://www.cnblogs.com/ghostcai/p/9275282.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107434.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pip卸载所有包_pip导出包

    pip卸载所有包_pip导出包pip批量完全卸载包

    2022年10月17日
  • 什么叫分销商_分销是什么意思「详细介绍」带你秒懂[通俗易懂]

    什么叫分销商_分销是什么意思「详细介绍」带你秒懂[通俗易懂]很多创业者在创业的道路上可能都会遇到一个问题那就是分销,但是很多创业者却又不懂分销是什么意思。今天我们抖音创业网大家详细地介绍一下关于分析的意思,绝对让你看完以后秒懂。分销是什么意思解释其实简单来说分销就是我们帮助别人销售商品,但是我们销售出去以后我们可以得到一定的分成,同时在我们的利润允许的情况下我们还可以继续拉下线,让其他的人成为我们的销售员工。分销实际案例模拟假如现在有一个苹果,供货商说这…

  • Pycharm汉化及衍生问题

    Pycharm汉化及衍生问题1、Pycharm是英文软件毫无疑问,pycharm是一款全英文的软件,对于英文一般的新手来说,使用起来上手较慢,于是汉化就是一种刚需。2、如何汉化网上查找,下载汉化包“resources_cn”,然后将“resources_cn”汉化包复制到“C:\ProgramFiles\JetBrains\PyCharmCommunityEdition2019.3\lib”(每个人的安装…

  • Kafka简明教程「建议收藏」

    Kafka简明教程「建议收藏」作者:柳树之www.jianshu.com/p/7b77723d4f96Kafka是啥?用Kafka官方的话来说就是:Kafkaisusedforbuildingreal-timedatapipelinesandstreamingapps.Itishorizontallyscalable,fault-tolerant,wickedfast,an…

    2022年10月17日
  • 密码学专题 SSL协议

    密码学专题 SSL协议SSL协议为不同的高层协议(http、FTP)提供安全服务 SSL握手协议、SSL修改密文协议和SSL告警协议的目的是为了管理和SSL相关的密文交换 连接:两台主机之间提供特定类型的数据传输,是点对点的关系;连接是短暂的,每一个连接都会和一个会话相互关联 会话:是指客户和服务器之间的关联,会话是通过握手协议创建的;会话是加密安全参数的一个集合,包含加密算法、临时的加密密钥等信息;会话可以为多个连接所共享,就可以避免为每个连接建立都要进行安全参数的协商带来的昂贵的时间代价。如果服务器和客户端之..

  • 马来西亚最大的电商平台_东南亚最受欢迎的跨境电商平台

    马来西亚最大的电商平台_东南亚最受欢迎的跨境电商平台一直以来,马来西亚电商市场几乎被Shopee和Lazada两大电商平台所统治,国际巨头占据主要市场。马来西亚电商平台TOP10中,Shopee和Lazada两大电商平台共占据了83.58%的网站流量,是马来电商入驻首选平台。然而直到2020年,Shopee超过了Lazada,拉开了距离,Shopee月均流量已达到Lazada的两倍以上。与此同时,马来西亚本土电商PGMall也在2020年的竞争中战胜Zalora与Lelong,稳固了他在马来西亚前三甲的地位。目前,无需注册马来西亚本地公司即可直接在

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号