@fuheimao
2014-11-21T21:20:22.000000Z
字数 939
阅读 686
NOIP2014
题解
无需判断是否越界的一种方法,就当是学习 C++ vector 和 map 的一个小栗子吧。
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
struct cross{
int x,y,num;
};
vector<cross> road;
map<int,int> ans;
int main(){
freopen("wireless.in","r",stdin);
freopen("wireless.out","w",stdout);
ios::sync_with_stdio(false);
int d,n,x,y,k;
cin>>d>>n;
for (int i=1;i<=n;i++){
cin>>x>>y>>k;
road.push_back((cross){x,y,k});//读入有公共场所的路口
}
for (int i=0;i<=128;++i){
for (int j=0;j<=128;++j){//枚举网格上每一个点
int temp=0;
//枚举每一个存在公共场所的路口是否在覆盖范围内,这样最多 129*129*20=332 820 次循环就能求出。
for (vector<cross>::iterator m=road.begin();m!=road.end();++m){
if (m->x<=i+d&&m->x>=i-d&&m->y<=j+d&&m->y>=j-d){
temp+=m->num;
}
}
if (temp){
ans[temp]++;
}
}
}
map<int,int>:: iterator q=ans.end();
q--;//由于 map 中的数据是排好序(默认从小到大)的,所以最后 map 中的最后一个就是最大的
cout<<q->second<<" "<<q->first<<endl;
return 0;
}
由于代码还没写,所以就先写思路吧。
从终点反向BFS即可得到与终点连通的点。
再遍历一次就可以得到该点是否可以出现在答案路径上(即该点的所有出边所指向的点都直接或间接与终点连通)。
然后求最短路就可以了。