poj 3686 The Windy's

本文主要是介绍poj 3686 The Windy's，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一开始把图建错了。结果纠结到现在。
本题需要拆点，把每台机器当成n台使用。
由于每台机器之前加工的玩具无法确定，但是我们可以反过来想。假设当前这个玩具倒数第K加工，那么他和后面加工的玩具总共延误K*MAP[I][J],我们就可以根据这个来建图。然后套KM算法去做。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define inf 1000001
int map[55][2500],visx[55],visy[2500],link[2500],lx[55],ly[2500],xx[55][2500];
double sum;
int n,m,x,t;
bool dfs(int i)
{
visx[i]=1;
for(int j=1;j<=m*n;j++)
{
if(visy[j]==0&&lx[i]+ly[j]-map[i][j]==0)
{
visy[j]=1;
if(link[j]==-1||dfs(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
void km()
{
for(int i=1;i<=n;i++)
{
lx[i]=-inf;
for(int j=1;j<=n*m;j++)
lx[i]=max(lx[i],map[i][j]);
}
memset(ly,0,sizeof(ly));  
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
{
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(i))  break;
int d=inf;
for(int j=1;j<=n;j++)
{
if(visx[j]==1)
for(int k=1;k<=m*n;k++)
if(visy[k]==0)
d=min(d,lx[j]+ly[k]-map[j][k]);
}
for(int j=1;j<=n;j++)
if(visx[j]==1)    lx[j]-=d;
for(int j=1;j<=n*m;j++)
if(visy[j]==1)    ly[j]+=d;
}
}
}          
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&xx[i][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
{
map[i][(k-1)*n+j]=-j*xx[i][k];
}
km();
for(int i=1;i<=n*m;i++)
{
if(link[i]!=-1)
sum+=map[link[i]][i];
}
printf("%.6lf\n",-1*sum/n);
}
return 0;
}

这篇关于poj 3686 The Windy's的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---