2 条题解

  • 0
    @ 2025-10-8 16:49:20
    #include <bits/stdc++.h>
    using namespace std;
    int match[110], chw[110], tsp;
    vector<int> G[110];
    bool findmuniu(int x)
    {
        for(int y : G[x])
        {
            if(chw[y] != tsp)
            {
                chw[y] = tsp;
                if(match[y] == 0 || findmuniu(match[y]) == 1)
                {
                    match[y] = x;
                    return 1;
                }
            }
        }
        return 0;
    }
    struct node{double x, y;}A[110], B[110];
    double dis(node n1, node n2){return sqrt( (n1.x - n2.x)*(n1.x - n2.x) + (n1.y - n2.y)*(n1.y - n2.y) );}
    int main()
    {
        int n, m; double s, v;
        while(scanf("%d%d%lf%lf", &n, &m, &s, &v) != EOF)
        {
            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);
            memset(G, 0, sizeof(G));
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    if(dis(A[i], B[j]) <= s * v)
                        G[i].emplace_back(j);
            int ans = 0;
            memset(match, 0, sizeof(match));
            memset(chw, 0, sizeof(chw));
            for(int i = 1; i <= n; i++)
            {
                tsp = i;
                if(findmuniu(i) == 1) ans++;
            }
            printf("%d\n", n - ans);
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:49:14
      • 1

      *【二分图:最大匹配】地鼠[Waterloolocal2001]

      信息

      ID
      317
      时间
      2000ms
      内存
      128MiB
      难度
      8
      标签
      递交数
      380
      已通过
      68
      上传者