hdu2426——Interesting Housing Problem
过得稀里糊涂，对最大权值的匹配还是不甚理解，明天继续！！！终于对此算法有点理解了！不过，下面这个发现有些BUG，另贴一个！
#include<stdio.h>#include<string.h>#define INF 0xfffffffint g,s,r,e;int lx,ly,my,stack;bool vx,vy;int find(int v){ int i,temp; vx=true; for(i=0;i<r;i++) { if(!vy) { temp=lx+ly-g; if(temp==0) { vy=true; if(my==-1||find(my)) { my=v; return true; } } else if(temp<stack) stack=temp; } } return false;}void KM(){ int i,j,min; for(i=0;i<s;i++) { lx=0; for(j=0;j<r;j++) if(lx<g) lx=g; } for(j=0;j<r;j++) ly=0; memset(my,-1,sizeof(my)); for(i=0;i<s;i++) { for(j=0;j<r;j++) stack=INF; while(1) { memset(vx,false,sizeof(vx)); memset(vy,false,sizeof(vy)); min=INF; if(find(i)) break; for(j=0;j<r;j++) { if(!vy&&stack<min) min=stack; } for(j=0;j<s;j++) if(vx) lx-=min; for(j=0;j<r;j++) { if(vy) ly+=min; else stack-=min; } } }}int main(){ int i,j,CASE=0,a,b,c,t; while(scanf("%d%d%d",&s,&r,&e)!=EOF) { if(e==0) printf("Case %d: %d\n",++CASE,-1); else { for(i=0;i<s;i++) for(j=0;j<r;j++) g=-INF; while(e--) { scanf("%d%d%d",&a,&b,&c); if(c>=0) g=c; } KM(); int ans=0,cnt=0; for(i=0;i<r;i++) { t=my; if(t>=0&&g!=-INF) { cnt++; ans+=g; } } if(cnt<s) ans=-1; printf("Case %d: %d\n",++CASE,ans); } } return 0;}
转：
#include<iostream>using namespace std;#define Max(a,b) (a)>(b) ? (a) : (b)#define Min(a,b) (a)<(b) ? (a) : (b)const int INF=0x7f7f7f7f;const int MAXN=501;int n,m,e,res;int w;int mat,slack;int lx,ly,vx,vy;bool dfs(int u){ int v,t; vx=1; for(v=0;v<m;++v) { if(!vy) { t=lx+ly-w; if(t==0) { vy=1; if(mat==-1||dfs(mat)) { mat=u;return true; } } else slack=Min(slack,t); } } return false;}bool km(){ memset(mat,-1,sizeof(mat)); memset(ly,0,m*sizeof(ly)); for(int i=0;i<n;++i) { lx=-INF; for(int j=0;j<m;++j) lx=Max(lx,w); if(lx==-INF) returnfalse; } for(int i=0;i<n;++i) { memset(slack,127,m*sizeof(slack)); while(true) { memset(vx,0,n*sizeof(vx)); memset(vy,0,m*sizeof(vy)); if(dfs(i)) break; int d=INF; for(int j=0;j<m;++j) if(!vy) d=Min(slack,d); for(int j=0;j<n;++j) if(vx) lx-=d; for(int j=0;j<m;++j) if(vy) ly+=d; } } int cnt=res=0; for(int i=0;i<m;++i) if(mat!=-1&&w]!=-INF) res+=w],cnt++; if(cnt==n) return true; return false;}int main(){ bool flag; int s,r,v,len,tmp,num=0; while(scanf("%d%d%d",&n,&m,&e)!=EOF) { flag=true; if(n>m) { flag=false; for(int i=0;i<e;++i) scanf("%d%d%d",&s,&r,&v); } else { for(int i=0;i<n;++i) for(int j=0;j<m;++j) w=-INF; for(int i=0;i<e;++i) { scanf("%d%d%d",&s,&r,&v); if(v>=0) w=v; } flag=km(); } printf("Case %d: ",++num); if(!flag) printf("-1\n"); else printf("%d\n",res); } return 0;}
页:
[1]