題目:有m個洞,n知動物,每個洞容一知動物,問當天敵來后最少有多少知動物不能逃亡。
沒看清楚最后的輸出,被坑了幾發
/************************************************ Author :DarkTong Created Time :2016/7/31 16:12:15 File Name :Pos_2536.cpp *************************************************///#include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define min(a, b) a<b?a:b #define max(a, b) a>b?a:b #define esp 1e-9 const int maxn = 100 + 10; int w[maxn][maxn], n, m; int Left[maxn]; bool used[maxn]; bool match(int j) {for(int i=1;i<=n;++i) if(w[i][j]&&!used[i]){used[i] = true;if(!Left[i]||match(Left[i])){Left[i] = j;return true;}}return false; } //返回最大匹配數 int hungary() {int res=0;memset(Left, 0, sizeof(Left));for(int i=1;i<=m;++i){memset(used, 0, sizeof(used));if(match(i)) res++;}return res; } double gx[maxn], gy[maxn], hx[maxn], hy[maxn];int main() {int T, cas=1;int s, v;while(scanf("%d%d%d%d", &n, &m, &s, &v)==4){memset(w, 0, sizeof(w));for(int i=1;i<=n;++i) scanf("%lf%lf", &gx[i], &gy[i]);for(int i=1;i<=m;++i) scanf("%lf%lf", &hx[i], &hy[i]);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){double l = (hx[j]-gx[i])*(hx[j]-gx[i]) +(hy[j]-gy[i])*(hy[j]-gy[i]);l = sqrt(l);if((double)s*v>=l) w[i][j]=1;}printf("%d\n", n-hungary());}return 0; }