首页 > 代码库 > poj1325 Machine Schedule
poj1325 Machine Schedule
有nx种A类机器,有ny种B类机器,k个东西,每个东西可以在a或b启动时生产(a属于A,b属于B),初始状态AB均在0,
每次切换需要重启,要生产全部k种东西,问至少重启几次。
将每件东西a,b建边,则每条边至少需要一个点才能完成该边代表的东西,题目等价于最小点覆盖问题,既用最少的点覆盖所有的边,
根据二分图性质,最小点覆盖数=最大匹配数
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> const int maxn=105; using namespace std; int e[maxn][maxn]; int vis[maxn]; int mx[maxn],my[maxn]; int nx,ny,n,k; int path(int u) { int v; for(v=0;v<ny;v++) { if(e[u][v]&&!vis[v]) { vis[v]=1; if(my[v]==-1||path(my[v])) { mx[u]=v; my[v]=u; return 1; } } } return 0; } int hungry() { int res=0; memset(mx,-1,sizeof mx); memset(my,-1,sizeof my); for(int i=0;i<nx;i++) { if(mx[i]==-1) { memset(vis,0,sizeof vis); res+=path(i); } } return res; } int main() { int a,b,c; while(scanf("%d",&nx)&&nx) { scanf("%d%d",&ny,&k); memset(e,0,sizeof e); while(k--) { scanf("%d%d%d",&a,&b,&c); if(!b||!c) continue;//此题中 含0的不用考虑 e[b][c]=1; } int ans=hungry(); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。