最省納智捷1年新車83萬起6檔好股票放一年賺5成輕忽小中風,當心變殘障台灣設計引領全球 雙鏡...
2012-05-13 11:38:10 人氣(389) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][二分圖最大匹配] 10080 - Gopher II

0
收藏
0
推薦

[UVA

Problem A: Gopher II

The gopher family, having averted the canine threat, must face a new predator.

The are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.

The input contains several cases. The first line of each case contains four positive integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances are in metres; all times are in seconds; all velocities are in metres per second.

Output consists of a single line for each case, giving the number of vulnerable gophers.

Sample Input

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Output for Sample Input

1


使用匈牙利算法, 每次去找增廣路徑, 每找到一條匹配數就多1,
因此最後的答案是 n-最大匹配數

#include <stdio.h>
#include <string.h>
#include <math.h>
int map[202][202], mt[202];
int mx[202], my[202], used[202];
int dfs(int x) {
int i, y;
for(i = 0; i < mt[x]; i++) {
y = map[x][i];
if(!used[y]) {
used[y] = 1;
if(my[y] == 0 || dfs(my[y])) {
mx[x] = y, my[y] = x;
return 1;
}
}
}
return 0;
}
int main() {
int n, m, s, v, i, j;
while(scanf("%d %d %d %d", &n, &m, &s, &v) == 4) {
double g[101][2], h[101][2];
for(i = 1; i <= n; i++)
scanf("%lf %lf", &g[i][0], &g[i][1]);
for(i = 1; i <= m; i++)
scanf("%lf %lf", &h[i][0], &h[i][1]);
memset(mt, 0, sizeof(mt));
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));

for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(sqrt((g[i][0]-h[j][0])*(g[i][0]-h[j][0])+
(g[i][1]-h[j][1])*(g[i][1]-h[j][1]))/v <= s) {
map[i][mt[i]++] = n+j;
}
}
}
int ans = 0;
for(i = 1; i <= n; i++) {
if(!mx[i]) {
memset(used, 0, sizeof(used));
if(dfs(i))
ans++;
}
}
printf("%d\n", n-ans);
}
return 0;
}
 

10080Gopher II二分圖最大匹配數
台長:Morris
人氣(389) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Math] 10310 - Dog and Gopher
此分類上一篇:[UVA] 11530 - SMS Typing

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文