大意：有一些n只松鼠，m个松鼠洞，以及他们行走的时间s，速度v，如果有一些松鼠不能进洞的话，那么他是脆弱的，请问使得产生最少“脆弱”的松鼠的行走方案是什么？最少有几只“脆弱”的松鼠。
思路：我们把问题转换一下，最少的“脆弱”松鼠->最大的进洞的松鼠。明显该图是二分图，那么我们以v*s为标准，如果两点间的距离dist<= v*s，那么则连一条边，否则不进行任何操作，然后问题就是经典的二分图最大匹配。
另外：宏定义 #define MAXM 210*210 竟然报错。。。CE N次。
CODE：
#include < string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAXN 210 #define MAXM 40010 // #define MAXM 210*210 UVA编译竟然报错。。。 struct node { double x, y; }a[MAXN], b[MAXN]; struct Edge { int v, next; }edge[MAXM]; int n, m, s, v; int cnt; int first[MAXN], link[MAXN]; bool vis[MAXN]; void init() { cnt = 0; memset(first, - 1, sizeof(first)); memset(link, - 1, sizeof(link)); } double dist( const node a, const node b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } int ED( int u) { for( int e = first[u]; e != - 1; e = edge[e].next) { int v = edge[e].v; if(!vis[v]) { vis[v] = true; if(link[v] == - 1 || ED(link[v])) { link[v] = u; return true; } } } return false; } void read_graph( int u, int v) { edge[cnt].v = v; edge[cnt].next = first[u], first[u] = cnt++; } void read_graph2() { for( int i = 1; i <= n; i++) { scanf( " %lf%lf ", &a[i].x, &a[i].y); } for( int i = 1; i <= m; i++) { scanf( " %lf%lf ", &b[i].x, &b[i].y); } double dis = s*v; for( int i = 1; i <= n; i++) { for( int j = 1; j <= m; j++) { double temp = dist(a[i], b[j]); if(temp <= dis) read_graph(i, j); } } } void solve() { int ans = 0; for( int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); if(ED(i)) ans++; } printf( " %d\n ", n-ans); } int main() { while(~scanf( " %d%d%d%d ", &n, &m, &s, &v)) { init(); read_graph2(); solve(); } return 0; }