poj 1698 二分图的匹配

本文主要是介绍poj 1698 二分图的匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简单的建图，X部是每部电影需要的天数之和，Y部是时间，建立二分图，然后就是匈牙利了。。。因为一开始乱初始化。。。match要-1的，我是从0开始计数的。。。Wa了超久。、。。。郁闷

#include<iostream>

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 51*51;
const int MAXM = 51*51;
bool mk[MAXN];
int n,m;
bool map[MAXN][MAXM];
int match[MAXN];
bool dfs(int u){
for(int i = 0;i<m;i++){
if(map[u][i] && !mk[i]){
mk[i] = true;
int t = match[i];
match[i] = u;
if(t==-1 || dfs(t))return true;
match[i] = t;
}
}
return false;
}
bool hungarian(){
int max_ = 0;
for(int i = 0;i<n;i++){
memset(mk,false,sizeof(mk));
if(dfs(i))
max_++;
}
///for(int i = 0;i<m;i++)printf("match[%d] =  %d\n",i,match[i]);
return max_>=n;
}
int main(){
int t;
scanf("%d",&t);
int k;
while(t--){
memset(match,-1,sizeof(match));  
memset(map,false,sizeof(map));
scanf("%d",&k);
n = 0;
m = 0;
while(k--){
int u[7];
for(int i = 0;i<7;i++)scanf("%d",&u[i]);
int d,w;
scanf("%d%d",&d,&w);
if(m<w)m = w;
for(int uu = 0;uu<7;uu++)if(u[uu]==1){
for(int i = n;i<n+d;i++)
for(int j = 0;j<w;j++)map[i][j*7+uu] = 1;
}
n+=d;
}
m = m*7;
/*for(int i = 0;i<n;i++){
printf("%d:",i);
for(int j = 0;j<m;j++)printf(" %d",map[i][j]);
printf("\n");
}*/
printf("%s\n",hungarian()?"Yes":"No");
}


return 0;
}

这篇关于poj 1698 二分图的匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---