Fair

wjh15101051's space

卧薪尝胆，厚积薄发。

Fair

Date: Fri Jul 06 19:31:45 CST 2018

In Category: NoCategory

Description：

每个点只生产一种物品，开一次展览需要至少 $s$ 种物品，所有边边权为一，问在每个点开展览的最小运输费用。

$1\le N \le 10^5,1\le M \le 10^5,k \le 100$

Solution：

多源 $bfs$ ，每次把生产所有某种物品的点都一次性放入队列中 $bfs$ ，即得到所有点获得第 $i$ 种物品的费用。

然后对于每个点把费用排序取前 $s$ 小即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,t,s;

#define MAXN 100005

int type[MAXN];

#define MAXK 100

int d[MAXN][MAXK];

bool v[MAXN][MAXK];

#define MAXM 100005

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&t,&s);

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

	{

		scanf("%d",&type[i]);

	}

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int c = 1;c <= t;++c)

	{

		queue<int> q;

		for(int k = 1;k <= n;++k)

		{

			if(type[k] == c)

			{

				q.push(k);

				d[k][c] = 0;

				v[k][c] = true;

			}

		}

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(!v[e[i].to][c])

				{

					d[e[i].to][c] = d[k][c] + 1;

					v[e[i].to][c] = true;

					q.push(e[i].to);

				}

			}

		}

	}

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

	{

		sort(d[i] + 1,d[i] + 1 + t);

		int ans = 0;

		for(int k = 1;k <= s;++k)

		{

			ans += d[i][k];

		}

		cout << ans << endl;

	}

	return 0;

}

In tag: 图论-BFS

wjh15101051