hdu1150 Machine Schedule
二分图的最小顶点覆盖数=最大匹配数
本题就是求最小顶点覆盖数的。
每个任务建立一条边。
最小点覆盖就是求最少的点可以连接到所有的边。本题就是最小点覆盖=最大二分匹配数。
注意一点就是:题目说初始状态为0,所以如果一个任务有一点为0的边不要添加。因为不需要代价
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; const int MAXN = 110; int uN,vN; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u){ int v; for(v=0;v<vN;v++){ if(g[u][v]&&!used[v]){ used[v]=true; if(linker[v]==-1||dfs(linker[v])){ linker[v]=u; return true; } } } return false; } int hungary(){ int res=0; int u; memset(linker,-1,sizeof(linker)); for(u=0;u<uN;u++){ memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; } int main() { int k; int i,u,v; while(scanf("%d",&uN),uN){ scanf("%d%d",&vN,&k); memset(g,0,sizeof(g)); while(k--){ scanf("%d%d%d",&i,&u,&v); if(u>0&&v>0) g[u][v]=1; } printf("%d\n",hungary()); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。