首页 > 代码库 > POJ 1325 Machine Schedule 二分图最大匹配

POJ 1325 Machine Schedule 二分图最大匹配

2024-07-15 00:47:51   230人阅读

把每一个任务看做一个边，机器的模式看做是一个点，这个其实就是求一个最少点覆盖所有边即最小点覆盖集的问题，因为最小点覆盖集=二分图的最大匹配，所以问题转化成了求二分图最大匹配问题。

第一次写二分图匹配，感觉建模还是相当困难的。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 200;bool g[maxn][maxn];int nx,ny,m;int bx[maxn],by[maxn];bool vis[maxn];int path(int now) {    for(int i = 1;i <= ny;i++) if(g[now][i] && !vis[i]) {        vis[i] = true;        if(!by[i] || path(by[i])) {            bx[now] = i; by[i] = now;            return 1;        }    }    return 0;}void solve() {    memset(bx,0,sizeof(bx));    memset(by,0,sizeof(by));    int ans = 0;    for(int i = 1;i <= nx;i++) {        if(!bx[i]) {            memset(vis,0,sizeof(vis));            ans += path(i);        }    }    printf("%d\n",ans);}int main() {    while(scanf("%d",&nx),nx) {        scanf("%d%d",&ny,&m);        memset(g,0,sizeof(g));        for(int i = 0;i < m;i++) {            int a,b,c; scanf("%d%d%d",&a,&b,&c);            g[b][c] = 1;        }        solve();    }    return 0;}

　　


联系
我们