CCF 201403-4 无线网络

试题编号： 201403-4

试题名称：无线网络

时间限制： 1.0s 内存限制： 256.0MB

问题描述

目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。
　　除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。
　　你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?

输入格式

第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)。
　　接下来 n 行,每行包含两个整数 xi 和 yi,表示一个已经放置好的无线路由器在 (xi, yi) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。
　　接下来 m 行,每行包含两个整数 xi 和 yi,表示 (xi, yi) 点处可以增设一个路由器。
　　输入中所有的坐标的绝对值不超过 108,保证输入中的坐标各不相同。

输出格式

输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路由器到第 2 个路由器最少经过的中转路由器的个数。

样例输入

5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0

样例输出

什么模型都不用建立，直接最短路，就能拿100！！！？？？

这数据，太~~~

#include<queue>
#include<stdio.h>
#include<iostream>
#define mp make_pair
#define pf(x) ((x)*(x))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pir;
const int N=205,M=N*N<<1;
const int inf=1e9;
struct edge{int v,w,next;}e[M];int tot,head[N];
int n,m,k,dis[N],pre[N];ll r;bool vis[N]; pir map[N];
inline void addedge(int x,int y,int z){
    e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
inline void add(int x,int y,int z=1){
    addedge(x,y,z);
    addedge(y,x,z);
}
inline void dijkstra(int S=1,int T=n){
    priority_queue<pir,vector<pir>,greater<pir> >q;
    for(int i=1;i<=n+m;i++) dis[i]=inf;
    dis[S]=0;
    q.push(mp(dis[S],S));
    while(!q.empty()){
        pir t=q.top();q.pop();
        int x=t.second;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int v=e[i].v;
            if(!vis[v]&&dis[v]>dis[x]+e[i].w){
                dis[v]=dis[x]+e[i].w;
                pre[v]=x;
                q.push(mp(dis[v],v)); 
            }
        }
    }
    printf("%d
",dis[T]-1);
}
inline bool dislen(int x,int y){
    return pf(map[x].fi-map[y].fi)+pf(map[x].se-map[y].se)<=r*r;
}
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d%d%d%lld",&n,&m,&k,&r);
    for(int i=1;i<=n+m;++i) scanf("%lld%lld",&map[i].fi,&map[i].se);
    for(int i=1;i<=n+m;++i){
        for(int j=i+1;j<=n+m;++j){
            if(dislen(i,j)){
                add(i,j);
            }
        }
    }
    dijkstra(1,2);
    return 0;
}

正解100

一个关键的问题：

m个点中可选k是不确定的, 怎么办, 难道我们还要遍历出所有可能的组合吗?

不用找出所有可能的情况, 只要在bfs的过程中记录我们使用的点有多少个在那k个点中, 如果刚好是k个, 那么就不能用了, 否则是可以用的. 即, 只要进行一次判断, 选择出循环的上界. 每次push进去一个点, 判断它是不是可选点, 如果是, 可选点数量就+1.

if(ck==k) lim=n;else lim=n+m;
for(int i=1;i<=lim;++i)
    //遍历下一个可供选择的点

最后注意坐标开long long

#include<queue>
#include<iostream>
#define pf(x) ((x)*(x))
using namespace std;
typedef long long ll;
const int N=205;
int n,m,k;ll r;bool vis[N];
struct node{
    ll x,y;int s,k;
    node(){}
    node(int x,int y,int s,int k):x(x),y(y),s(s),k(k){}
}g[N];
void bfs(int S=1,int T=2){
    queue<node>q;
    q.push(node(g[S].x,g[S].y,0,0));
    vis[1]=1;
    while(!q.empty()){
        node h=q.front();q.pop();
        ll cx=h.x,cy=h.y;int cs=h.s,ck=h.k,lim;
        if(cx==g[T].x&&cy==g[T].y){printf("%d
",cs-1);return ;}
        if(ck==k) lim=n;else lim=n+m;
        for(int i=1;i<=lim;++i){
            if(vis[i]||pf(g[i].x-cx)+pf(g[i].y-cy)>r) continue;
            vis[i]=1;
            q.push(node(g[i].x,g[i].y,cs+1,ck+(i>n)));
        }
    }
}
int main(){
    scanf("%d%d%d%lld",&n,&m,&k,&r);r=r*r;
    for(int i=1;i<=n+m;++i) scanf("%lld%lld",&g[i].x,&g[i].y);
    bfs();
    return 0;
}