蓝桥杯在线测试的题解(二）

蓝桥杯在线测试的题目。不定时不断更新中,没按顺序做。

题目地址：http://lx.lanqiao.org/index.page

上一次的因为太长，保存好慢，决定在开一篇。

上一篇：蓝桥杯在线测试的题解（一）http://blog.csdn.net/murmured/article/details/18908567

算法训练- 安慰奶牛  

Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

题目的测试样例有误：（P为7怎么才6组。。我把题目的7改为6答案为178）

5 6
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

思路：

直接把边的权值w（u,v）改为2*w（u,v）+cost[u]+cost[v]，然后求MST。why?

纸上画画这组数据（答案43）

3 2
5 6 7
1 2 3 
2 3 4

然后因为他要找一个地方过夜，所以要多花费一个点的对话，找最小的地方过夜就好了~嘻嘻~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000+10;
const int MAXM=100000+10;
const int INF=100000;
int cost[MAXN],fa[MAXN];
int find(int cur)
{
	return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);
}
struct edge
{
	int from,to,val;
	bool operator <(const edge& x)const{
		return val<x.val;
	}
}e[MAXM];

int main()
{
	int mini=INF,index;
	int n,p;
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&cost[i]);
		mini=min(cost[i],mini);
		fa[i]=i;
	}
	for(int i=0;i<p;i++)
	{
		scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
		e[i].val=(e[i].val<<1)+cost[ e[i].from ] + cost [ e[i].to ];
	}
	sort(e,e+p);
	int ans=0;
	for(int i=0;i<p;i++)
	{
		int x=e[i].from,y=e[i].to;
		int root_x=find(x),root_y=find(y);
		if(root_x==root_y)   continue;
		fa[root_x]=root_y;
		ans+=e[i].val;
	}
	printf("%d\n",ans+mini);
	return 0;
}

算法训练- 最短路

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

直接SPFA，直接100分。。

开锦囊说堆优化的dijkstra。。。题目有负边权啊！你确定这不是临时工写的？还是我水平有限?望赐教。。。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=20000+10;
const int MAXM=200000+10;
const int INF=100000;
int head[MAXN],len,dis[MAXN],n,m;
bool vis[MAXN];
struct edge
{
	int to,val,next;
}e[MAXM];

void add(int from,int to,int val)
{
	e[len].to=to;
	e[len].val=val;
	e[len].next=head[from];
	head[from]=len++;
}
queue<int> q;
void spfa()
{
	for(int i=1;i<=n;i++)
		dis[i]=INF;
	memset(vis,0,sizeof(vis));
	q.push(1);
	vis[1]=true;
	dis[1]=0;
	while(!q.empty())
	{
		int cur=q.front();
		q.pop();
		vis[cur]=false;
		for(int i=head[cur];i!=-1;i=e[i].next)
		{
			int id=e[i].to;
			if(dis[id] > dis[cur] + e[i].val)
			{
				dis[id] = dis[cur] + e[i].val;
				if(!vis[id])
				{
					vis[id]=true;
					q.push(id);
				}
			}
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	len=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int from,to,val;
		scanf("%d%d%d",&from,&to,&val);
		add(from,to,val);
	}
	spfa();
	for(int i=2;i<=n;i++)
		printf("%d\n",dis[i]);

	return 0;
}

蓝桥杯在线测试的题解(二）

原文：http://blog.csdn.net/murmured/article/details/19292147