[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=;

inline int rd(){

  int ret=,f=;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-:;

  while(isdigit(c))ret=ret*+c-'',c=getchar();

  return ret*f;

}

struct Edge{

  int next,to;

}e[MAXN<<];

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][],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=;i<=n;i++) if(typ[i]==x) Q.push(i),dis[i][x]=;

  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]+){

          dis[v][x]=dis[top][x]+;

          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=;i<=n;i++) typ[i]=rd();

  int x,y,w;

  for(int i=;i<=m;i++){

    x=rd();y=rd();

    add(x,y);add(y,x);

  }

  for(int i=;i<=k;i++) bfs(i);

  int ret=;

  for(int i=;i<=n;i++){

    V.clear();

    for(int j=;j<=k;j++) V.push_back(dis[i][j]);

    sort(V.begin(),V.end());

    ret=;

    for(int j=;j<s;j++) ret+=V[j];

    printf("%d ",ret);

  }

  return ;

}

巴特西

[CF] 986 A. Fair

最新文章

热门文章