程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3686 The Windys

POJ 3686 The Windys

編輯:C++入門知識

The Windy's
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 3299   Accepted: 1413

Description

The Windy's is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Zij hours if the toys are making in the j-th workshop. Moreover, each order's work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.

The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50).
The next N lines each contain M integers, describing the matrix Zij (1 ≤ Zij ≤ 100,000) There is a blank line before each test case.

Output

For each test case output the answer on a single line. The result should be rounded to six decimal places.

Sample Input

3

3 4
100 100 100 1
99 99 99 1
98 98 98 1

3 4
1 100 100 100
99 1 99 99
98 98 1 98

3 4
1 100 100 100
1 99 99 99
98 1 98 98
Sample Output

2.000000
1.000000
1.333333

Source

POJ Founder Monthly Contest – 2008.08.31, windy7926778
[cpp]
/***************************************************************
    > File Name:    POJ3686.cpp
    > Author:       SDUT_GYX
    > Mail:         [email protected]
    > Created Time: 2013/6/4 0:16:38
 **************************************************************/ 
 
#include <iostream>  
#include <cstring>  
#include <algorithm>  
#include <cstdio>  
#include <queue>  
#include <cstdlib>  
#include <iomanip>  
#include <string>  
#include <vector>  
#include <map>  
#include <cmath>  
#include <stack>  
#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; 

/***************************************************************
 > File Name:    POJ3686.cpp
 > Author:       SDUT_GYX
 > Mail:         [email protected]
 > Created Time: 2013/6/4 0:16:38
 **************************************************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#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. 下一頁:
Copyright © 程式師世界 All Rights Reserved