題意：
? ? ?有n只老鼠，m個洞，每個洞最多可以藏一只老鼠，每個老鼠的移動速度都是v，給你他們的當前坐標，和洞的坐標，突然老鷹來了，他們必須在s秒內跑到一個洞藏起來，問你最少有多少只老鼠被抓走了。


思路：

? ? ? 二分圖匹配裸題，關鍵就是那句一個洞最多容一只老鼠，對于每個老鼠連接能在s秒內到達的所有洞，然后一邊最大匹配，得到的就是最大的藏起來的老鼠sum，輸出n - sum就是最少的被抓走的老鼠。

#include<stdio.h> #include<math.h> #include<string.h>#define N_node 100 + 10 #define N_edge 10000 + 100typedef struct {int to ,next; }STAR;typedef struct {double x ,y; }NODE;STAR E[N_edge]; NODE node1[N_node] ,node2[N_node]; int list[N_node] ,tot; int mk_dfs[N_node] ,mk_gx[N_node];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }double dis(NODE a ,NODE b) {double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);return sqrt(tmp); }int DFS_XYL(int s) {for(int k = list[s] ;k; k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = s;return 1;}}return 0; }int main () {int n ,m ,i ,j;double s ,v;while(~scanf("%d %d %lf %lf" ,&n ,&m ,&s ,&v)){for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node1[i].x ,&node1[i].y);for(i = 1 ;i <= m ;i ++)scanf("%lf %lf" ,&node2[i].x ,&node2[i].y);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){if(dis(node1[i],node2[j]) / v <= s)add(i ,j);}memset(mk_gx ,255 ,sizeof(mk_gx));int sum = 0;for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));sum += DFS_XYL(i);}printf("%d\n" ,n - sum);}return 0; }

??

總結

以上是生活随笔為你收集整理的POJ2536 二分图匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。