NOIP模拟——救援行动

75 阅读 0 评论 50 点赞

我是靠谱客的博主苗条绿茶，最近开发中收集的这篇文章主要介绍NOIP模拟——救援行动，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述 Description

【问题描述】
　　有一个城市遭受了大水灾，现在等待救援中。这个城市共有n个村庄，每个村庄的人口数量为a[i]。由于遭受洪水冲击，村庄与村庄之间的很多道路遭受了严重的破坏。为了方便救援，救援总部用卫星拍了地图，然后工程师根据地图，把这些村落之间的道路做出了标记。(x,y,1)表示村庄x和y是相通的,(x,y,0)表示村庄x和y的道路遭到破坏。考虑到受灾后，灾民之间肯定会开展互相救助，如果有两个村落是连通的，那么就互相称为邻居，如果某个村落没有道路相连，就意味着没有了邻居，我们称为"孤岛"村。明显，邻居越多的村落受灾情况肯定会小点，而且自救的可能性也大点。所以我们在救援时肯定优先救援孤岛村，然后再考虑邻居最少的村落……依次展开救援。
由于救援队一共只有一架直升机，且知道飞机容量最多V人。
直升机去救援时的注意点：
1：一次救援只能去一个村庄，救了人后必须返回，不能中途去另外的村庄
2：由于飞机油量不足，最多只能求援K次。
3：救援时优先救援“孤岛”村落，只有没有"孤岛"村落才会去救邻居最少的村落、然后再就邻居次少的村落……依次类推。
下面给出m对卫星拍摄的村庄关系图，请你根据这些资料展开救援。
当然希望这次救援救出最多的灾民。
【输入】help.in
第一行两个整数m,n. m表示有m条村庄之间的道路信息。n表示共有n村庄
第二行n个整数，依次表示编号1~n每个村庄的等待救援人数。
后面m行,每行3个整数(x,y,1)或者(x,y,0)，x<y,表示村庄号x和村庄号y是否有路连通。
最后一行V和k两个整数表示飞机容量和救援的次数。
【输出】help.out
一个整数表示最多能救出多少灾民。

样例输入 Sample Input

样例输入（一）:
2 3
3 4 5
1 2 1
2 3 1
4 2
样例输入（二）：
8 7
2 3 5 7 5 3 5
1 2 1
1 3 1
2 4 1
2 5 0
3 5 1
4 5 0
6 7 0
5 6 0
6 3

样例输出 Sample Output
	样例输出（一） 7 说明：村庄1和3邻居都只有一个，然后先从3号村庄救出4人，再从1号村庄救出3人。最终救援人数3+4=7 样例输出（二）： 14 说明：村庄6和7是孤岛，先去救援他们，两次救援的人数为3+5=8人.第三次救援村庄4，它只有1个邻居。所以最终救援人数8+6=14

时间限制：所有句子相加不超过1亿句。 1亿就是1秒

空间限制：所有数组相加不超过1000万。约40M内存

文件输入输出设置　

对于10%的数据，所有村庄道路全毁。
对于30%的数据, 待救援的村庄数量n<=500
对于80%的数据，待救援的村庄数量n<=10000, 飞机救援次数k<=1000
对于100%的数据，待救援的村庄数量n<=10000，每个村庄的人数a[i]<=10000，m<=5000000。飞机容量V<=3000,K<=10000

个人觉得本题可谓千年第一“好”题……

真的是，废话一堆，搞得人兴高采烈（tou hun nao zhang），以为是做图，实际上不就先排个序再查找嘛……

如果直接线性查找，倒也可以勉强满分，但可以优化一下，建一个大根堆，因为它每次就找最大的那个嘛。

详见注释，还有看不懂的就评论。

#include<bits/stdc++.h>
using namespace std;
struct STU
{
	int man,road;
}a[10005],t;
int n,m,k,v,i,x,y,p,ans,nn;
bool cmp(STU x,STU y)
{
	if(x.road>y.road)return 1;
	if(x.road==y.road&&x.man<y.man)return 1;
	return 0;
}
int main()
{
	cin>>m>>n;
	for(i=1;i<=n;i++)
	  cin>>a[i].man;
	for(i=1;i<=m;i++)
	{
		cin>>x>>y>>p; 
		if(p==1)
		{
			a[x].road++;
			a[y].road++;
		}
	}	
	cin>>v>>k;
	make_heap(a+1,a+n+1,cmp);//按度建立小根维,度一样人数多的在上面
	nn=n;
	for(i=1;i<=k;i++)
	{
		t=a[1];//取堆顶
		pop_heap(a+1,a+nn+1,cmp);//o[1]出雄
		nn--;
		if(t.man>v)//如果堆顶人数超过飞机容量
		{
		  t.man-=v;//把剩余的人数插入堆。
	      a[++nn]=t;
		  push_heap(a+1,a+nn+1,cmp);
		  ans+=v;//飞机激走满容量。
		}
		else ans+=t.man;//没超过飞机，全部激走。
	}
	cout<<ans;
}

且慢，点个赞再走吧！