(UVA) 11159 - Factors and Multiples [二分圖最大匹配]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2100

想法：演算法筆記

複雜度：O(V * V^2) ，其中如果用vector存邊，可以壓成 O(VE)

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 106;

int adj[MAX_N][MAX_N];

int a[MAX_N];
int b[MAX_N];
int match[MAX_N];
int vis[MAX_N];

bool dfs(int i) {
//    cout<<"i = "<<i<<endl;
    for (int j=1;MAX_N>j;j++) {
        if (!adj[i][j] || vis[j]) continue;
        vis[j]=true;
        if (!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

int main () {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int T;
    scanf("%d",&T);
    int cases=0;
    while (T--) {
        int n,m;
        scanf("%d",&n);
        for (int x=1;n>=x;x++) {
            scanf("%d",&a[x]);
        }
        scanf("%d",&m);
        for (int x=1;m>=x;x++) {
            scanf("%d",&b[x]);
        }
        memset(adj,0,sizeof(adj));
        for (int i=1;n>=i;i++) {
            for (int j=1;m>=j;j++) {
                if (a[i] && b[j] % a[i] == 0) {
                    adj[i][j]  = 1;
                }
                if (!b[j]) {
                    adj[i][j]  = 1;
                }
            }
        }
        int ans=0;
        memset(match,0,sizeof(match));
        for (int i=1;n>=i;i++) {
            memset(vis,0,sizeof(vis));
            ans += dfs(i);
//            cout << "i = "<<i<<" , ans = "<<ans<<endl;
        }
        printf("Case %d: %d\n",++cases,ans);
    }
}