POJ 3686 The Windy's - c++编程基础

TOP

POJ 3686 The Windy's (二)

2015-11-21 01:21:52 来源: 作者: 【大中小】浏览:12次

int d=inf;?
??????????? for(int i=1;i<=m;i++)?
??????????? {?
??????????????? if(!visity[i])?
??????????????? {?
??????????????????? d = min(d,slack[i]);?
??????????????? }?
??????????? }?
??????????? for(int i=1;i<=n;i++)?
??????????? {?
??????????????? if(visitx[i])?
??????????????? {?
??????????????????? lx[i] -=d;?
??????????????? }?
??????????? }?
??????????? for(int i=1;i<=m;i++)?
??????????? {?
??????????????? if(visity[i])?
??????????????? {?
??????????????????? ly[i] +=d;?
??????????????? }else?
??????????????? {?
??????????????????? slack[i] -=d;?
??????????????? }?
??????????? }?
??????? }?
??? }?
??? int s=0;?
??? for(int i=1;i<=m;i++)?
??? {?
??????? if(linky[i])?
??????? {?
??????????? int j=linky[i];?
??????????? s+=w[j][i];?
??????? }?
??? }?
??? return -s;?
}?

/***************************************************************
?> File Name:??? POJ3686.cpp
?> Author:?????? SDUT_GYX
?> Mail:???????? 2272902662@qq.com
?> Created Time: 2013/6/4 0:16:38
?**************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define N 3600
#define inf 0x7ffffff
using namespace std;
int lx[N],ly[N],slack[N],linky[N],w[N][N],n,m;
bool visitx[N],visity[N];
int main()
{
?//freopen("data1.in","r",stdin);
?int KM();
?int t;
?scanf("%d",&t);
?while(t--)
?{
??scanf("%d %d",&n,&m);
??int x;
??for(int i=1;i<=n;i++)
??{
???for(int j=1;j<=m;j++)
???{
????scanf("%d",&x);
????for(int k=1;k<=n;k++)
????{
?????w[i][(j-1)*n + k] = -x*k;
????}
???}
??}
??m=n*m;
??int res=KM();
??printf("%.6lf\n",(double)res/n);
?}
?return 0;
}
bool find(int k)
{
?visitx[k] = true;
?for(int i=1;i<=m;i++)
?{
??if(visity[i])
??{
???continue;
??}
??int t=lx[k] + ly[i] - w[k][i];
??if(t==0)
??{
???visity[i] = true;
???if(!linky[i]||find(linky[i]))
???{
????linky[i] = k;
????return true;
???}
??}else
??{
???slack[i]=min(slack[i],t);
??}
?}
?return false;
}
int KM()
{
?memset(ly,0,sizeof(ly));
?memset(linky,0,sizeof(linky));
?for(int i=1;i<=n;i++)
?{
??lx[i] = -inf;
?}
?for(int i=1;i<=n;i++)
?{
??for(int j=1;j<=m;j++)
??{
???lx[i] = max(lx[i],w[i][j]);
??}
?}
?for(int i=1;i<=n;i++)
?{
??for(int j=1;j<=m;j++)
??{
???slack[j] = inf;
??}
??while(1)
??{
???memset(visitx,false,sizeof(visitx));
???memset(visity,false,sizeof(visity));
???if(find(i))
???{
????break;
???}
???int d=inf;
???for(int i=1;i<=m;i++)
???{
????if(!visity[i])
????{
?????d = min(d,slack[i]);
????}
???}
???for(int i=1;i<=n;i++)
???{
????if(visitx[i])
????{
?????lx[i] -=d;
????}
???}
???for(int i=1;i<=m;i++)
???{
????if(visity[i])
????{
?????ly[i] +=d;
????}else
????{
?????slack[i] -=d;
????}
???}
??}
?}
?int s=0;
?for(int i=1;i<=m;i++)
?{
??if(linky[i])
??{
???int j=linky[i];
??????????? s+=w[j][i];
??}
?}
?return -s;
}

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2488 A Knight's Journey	下一篇：uva 11178 - Morley's Theore..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: