首页 > 系统服务 > 详细

HDU [P1150] Machine Schedule

时间:2018-01-12 22:20:24      阅读:86      评论:0      收藏:0      [点我收藏+]

标签:schedule   blog   sin   hdu   int   out   ++   pos   urn   

二分图匹配求最小点覆盖

把两个机器作为两个集合,把每个任务当做边建图.那么所求的就是二分图的最小点覆盖.
但是最开始WA了,原因在于,题目要求的是变换的次数,也就是与0连的边需要删去.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
int n,m,k,g[105][105],match[105];
bool f[105];
bool hungarian(int u){
    for(int i=1;i<=g[u][0];i++){
        int v=g[u][i];
        if(!f[v]){
            f[v]=1;
            if(match[v]==-1||hungarian(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    while(1){
        n=init();
        if(!n) break;
        m=init();k=init();
        memset(g,0,sizeof(g));
        for(int i=0;i<=n;i++) match[i]=-1;
        for(int i=1;i<=k;i++){
            int t=init(), u=init(),v=init();
            if(u&&v) g[u][++g[u][0]]=v;
        }
        int ans=0;
        for(int i=1;i<n;i++){
            memset(f,0,sizeof(f));
            if(hungarian(i)) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

HDU [P1150] Machine Schedule

标签:schedule   blog   sin   hdu   int   out   ++   pos   urn   

原文:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8277732.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号