首页 > 代码库 > hdu5045：带权二分图匹配
hdu5045：带权二分图匹配
题目大意 ：
n个人 做m道题，其中 每连续的n道必须由不同的人做
已知第i人做出第j题的概率为pij，求最大期望
思路：
考虑每连续的n道题 都要n个人来做，显然想到了带权的二分图匹配
然后就是套模板了
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>#include<math.h>#include <cstring>using namespace std;#define MAXN 15int n,m;int m1[15];int m2[15];double value[1010][15];bool xiangdeng(double a,double b){ if(fabs(a-b)<0.00000001) return 1; return 0;}double fuck(int m,int n,double Gragh_gailv[][MAXN]){ int s[MAXN],t[MAXN]; double l1[MAXN],l2[MAXN]; int p,q,index,j,k; double value_return=0; for(index=0;index<m;index++) { l1[index]=-10000000; for(j=0;j<n;j++) l1[index]=Gragh_gailv[index][j]>l1[index]?Gragh_gailv[index][j]:l1[index]; if(xiangdeng(l1[index],-10000000)) return -1; } for(index=0;index<n;index++) l2[index]=0; memset(m1,-1,sizeof(m1)); memset(m2,-1,sizeof(m2)); for(index=0;index<m;index++) { memset(t,-1,sizeof(t)); p=0;q=0; for(s[0]=index;p<=q&&m1[index]<0;p++) { for(k=s[p],j=0;j<n&&m1[index]<0;j++) { if(xiangdeng(l1[k]+l2[j],Gragh_gailv[k][j])&&t[j]<0) { s[++q]=m2[j]; t[j]=k; if(s[q]<0) { for(p=j;p>=0;j=p) { m2[j]=k=t[j]; p=m1[k]; m1[k]=j; } } } } } if(m1[index]<0) { index--; double pp=10000000; for(k=0;k<=q;k++) { for(j=0;j<n;j++) { if(t[j]<0&&l1[s[k]]+l2[j]-Gragh_gailv[s[k]][j]<pp) pp=l1[s[k]]+l2[j]-Gragh_gailv[s[k]][j]; } } for(j=0;j<n;j++) l2[j]+=t[j]<0?0:pp; for(k=0;k<=q;k++) l1[s[k]]-=pp; } } for(index=0;index<m;index++) value_return+=Gragh_gailv[index][m1[index]]; return value_return;}int main(){ #ifndef ONLINE_JUDGE freopen("shu.txt","r",stdin); #endif int t; scanf("%d",&t); int cas=0; while(t--) { double ans=0; cas++; scanf("%d%d",&n,&m); memset(value,0,sizeof(value)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) scanf("%lf",&value[j][i]); } for(int i=0;i<m;i+=n) { int e=i+n-1>=m?m-1:i+n-1; ans+=fuck(e-i+1,n,value+i); } printf("Case #%d: %.5f\n",cas,ans); } return 0;}
hdu5045：带权二分图匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。