【HDU 1150】Machine Schedule(二分图匹配)
HDU 匹配 二分 MACHINE Schedule
2023-09-11 14:19:25 时间
机器的不同模式为点,对于每个job,建两条边 A机器需要的模式<->B机器需要的模式。
问题转化为最小点覆盖,然后用二分图的最小点覆盖==最大匹配,用匈牙利算法解。
#include <cstdio> #include <cstring> const int N=105<<1; const int M=1001<<1; struct edge{ int to,next; }e[M]; int head[N],tot; void add(int u,int v){ e[tot].to=v;e[tot].next=head[u];head[u]=tot++; } void init(){ tot=0; memset(head,-1,sizeof head); } int n,vis[N],link[N]; int find(int u) { for(int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(!vis[v]){ vis[v]=1; if(!link[v]||find(link[v])){ link[v]=u; return 1; } } } return 0; } int solve(){ memset(link,0,sizeof link); int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(find(i))ans++; } return ans; } int main(){ int k,m,u,v; while(scanf("%d",&n),n){ init(); scanf("%d%d",&m,&k); while(k--){ scanf("%d%d%d",&m,&u,&v); add(u,v+n); add(v+n,u); } printf("%d\n",solve()); } }
相关文章
- hdu 1789 Doing Homework again 贪心
- HDU 3442 Three Kingdoms(状态压缩 + BFS )
- 【hdu 2955】Robberies
- 【hdu 4135】Co-prime
- 【hdu 2108】Shape of HDU
- HDU 1533 Going Home(KM完美匹配)
- HDU 5280 Senior's Array 最大区间和
- HDU 5071 Chat(2014鞍山B,模拟)
- HDU 3304 Interesting Yang Yui Triangle lucas定理
- HDU 4825 Xor Sum
- hdu 3123 GCC (2009 Asia Wuhan Regional Contest Online)
- HDU 1068 Girls and Boys(最大独立集合 = 顶点数 - 最大匹配数)
- HDU 1085 Holding Bin-Laden Captive! (母函数)
- hdu 2594 Simpsons’ Hidden Talents 【KMP】
- HDU 1599 find the mincost route