程式碼備份區

題意：

有很n隻地鼠以及很m個地鼠洞，地鼠要在s秒內跑到洞裏面材行躲過老鷹的攻擊，然後地鼠跑的速度是v

問說地鼠死最少的情況下有幾隻地鼠會死

解法：

把地鼠跟地鼠洞做matching，可以改成maximum flow去做，如果地鼠跟地鼠洞距離 < s*v表示他有機會可以躲進這個洞裏面

這題感覺沒有誤差的問題

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int map[234][234];
int n,m,s,v,e;
double p[234][2];

double dis(int a,int b){
    return sqrt((p[a][0]-p[b][0])*(p[a][0]-p[b][0])+(p[a][1]-p[b][1])*(p[a][1]-p[b][1]));
}

void creatGraph(){
    int i,j;
    double bound = s*v;
    memset(map,0,sizeof(map));
    e = n+m+1;
    for(i=1;i<=n;++i)map[0][i] = 1;
    for(i=1;i<=m;++i)map[n+i][e] = 1;
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            if(dis(i,n+j) < bound ){
                map[i][n+j] = 1;
            }
        }
    }
}

int q[234];
int inQ[234];
int pre[234];
int spfa(){
    int qs,qe;
    int i;
    memset(pre,-1,sizeof(pre));
    memset(inQ,0,sizeof(inQ));
    qs = qe = 0;
    q[qe++] = 0;
    inQ[0] = 1;
    while(qs != qe){
        for(i=0;i<=e;++i){
            if(map[q[qs]][i] && !inQ[i]){
                inQ[i] = 1;
                q[qe++] = i;
                pre[i] = q[qs];
                if(i == e)return 1;
            }
        }
        ++qs;
    }
    return 0;
}

int flow(){
    int i,j;
    while(spfa()){
        for(i=e,j=pre[i];j!=-1;i=j,j=pre[i]){
            --map[j][i];
            ++map[i][j];
        }
    }
    for(i=j=0;i<e;++i){
        if(map[e][i])++j;
    }
    return j;
}

int main(){
    int i;
    while(scanf("%d %d %d %d",&n,&m,&s,&v)!=EOF){
        for(i=1;i<=n;++i){
            scanf("%lf %lf",&p[i][0],&p[i][1]);
        }
        for(i=1;i<=m;++i){
            scanf("%lf %lf",&p[n+i][0],&p[n+i][1]);
        }
        creatGraph();
        printf("%d\n",n-flow());
    }
    return 0;
}