首页 > 代码库 > 【POJ 1698】Alice's Chance(二分图多重匹配)
【POJ 1698】Alice's Chance(二分图多重匹配)
http://poj.org/problem?id=1698
电影和日子匹配,电影可以匹配多个日子。
最多有maxw*7个日子。
二分图多重匹配完,检查一下是否每个电影都匹配了要求的日子那么多。
#include<cstdio>#include<cstring>#include<algorithm>#define N 360#define M 30using namespace std;int t,n,m;int g[N][M];int linker[M][N],num[M];bool vis[M];bool dfs(int u){ for(int v=0;v<m;v++) if(g[u][v]&& !vis[v]){ vis[v]=1; if(linker[v][0]<num[v]){ linker[v][++linker[v][0]]=u; return 1; } for(int i=1;i<=num[v];i++) if(dfs(linker[v][i])){ linker[v][i]=u; return 1; } } return 0;}int hungary(){ int res=0; for(int i=0;i<m;i++) linker[i][0]=0; for(int u=0;u<n;u++){ memset(vis,0,sizeof vis); if(dfs(u))res++; } return res;}bool solve(){ hungary(); for(int i=0;i<m;i++){ // printf("{%d}",linker[i][0]); if(linker[i][0]!=num[i]) return 0; } return 1;}int main(){ scanf("%d",&t); while(t--){ scanf("%d",&m); memset(g,0,sizeof g); int maxw=0; for(int i=0;i<m;i++) { for(int j=0;j<7;j++) scanf("%d",&g[j][i]); int w; scanf("%d%d",&num[i],&w); maxw=max(maxw,w); for(int j=0;j<7;j++)if(g[j][i]) for(int k=1;k<w;k++) g[j+k*7][i]=1; } n=maxw*7; if(solve())puts("Yes"); else puts("No"); } return 0;}
【POJ 1698】Alice's Chance(二分图多重匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。