POJ 3686 The Windy's

POJ 3686 The Windy's

題目概述:腦書p.248

有N個玩具，M個工廠。第i個玩具在j號工廠製作需要Zi,j的時間，工廠不能同時做兩個東西，需要等一個做完才能做下一個。假設某個工廠要做花費時間2和5的東西，那兩個玩具的總製作時間為2+(2+5)=9。求做好個玩具的平均時間最小值。

思路:

最小花費最大流。

看了腦書才會做的QQ

他有一個很重要的思維是，假設一個工廠要做k=3個玩具(時間為2,3,5)，那總花費時間為(2)+(2+3)+(2+3+5)，可以發現2出現了3次，所以第1個做的東西貢獻了k倍自己花費的時間，第2個東西貢獻了k-1倍自己花費的時間。

然後用上面的例子來說，如果只看一個工廠，要使總花費最小需要greedy得先製作花費最少的。

把每一個工廠分成n個點........

詳情請見code或腦書吧

真的有點難描述...(我累了

待補QQ

//By SCJ

#include<iostream>

#include<vector>

using namespace std;

#define endl '\n'

#define maxn 3000

#define INF 1000000000

#define end END

int n,m,end;

struct Edge{

   int to,cost,cap,rev;

   Edge(int _to,int _cost,int _cap,int _rev)

   {

       to=_to;cost=_cost;cap=_cap;rev=_rev;

   }

};

vector<Edge> G[maxn];//1~n->obj  n+1~2n->1fec 2n+1~3n->2fec

void add_Edge(int from,int to,int cost,int cap)

{

   G[from].push_back(Edge(to,cost,1,G[to].size()));

   G[to].push_back(Edge(from,-cost,0,G[from].size()-1));

}

int prevv[maxn],preve[maxn],d[maxn];

void init()

{

   for(int i=0;i<maxn;++i) G[i].clear();

   scanf("%d%d",&n,&m);

   for(int i=1;i<=n;++i)

   {

       for(int j=1;j<=m;++j)

       {

           int tp;scanf("%d",&tp);

           for(int k=1;k<=n;++k)

           {

               add_Edge(i,j*n+k,tp*k,1);

           }

       }

   }

   end=(m+1)*n+1;

   for(int i=1;i<=n;++i)

       add_Edge(0,i,0,1);

   for(int i=n+1;i<=(m+1)*n;++i)

       add_Edge(i,end,0,1);

}

double solve()

{

   int res=0;

   while(1)

   {

       for(int i=0;i<=end;++i) d[i]=INF;

       d[0]=0;

       bool update=1;

       while(update)

       {

           update=0;

           for(int i=0;i<=end;++i)

           {

               for(int j=0;j<G[i].size();++j)

               {

                   Edge e=G[i][j];

                   if(e.cap>0&&d[e.to]>d[i]+e.cost)

                   {

                       update=1;

                       d[e.to]=d[i]+e.cost;

                       prevv[e.to]=i;

                       preve[e.to]=j;

                   }

               }

           }

       }

       if(d[end]==INF) break;

       int t=INF;

       for(int i=end;i!=0;i=prevv[i])

       {

           Edge &e=G[prevv[i]][preve[i]];

           t=min(t,e.cap);

       }

       for(int i=end;i!=0;i=prevv[i])

       {

           Edge &e=G[prevv[i]][preve[i]];

           e.cap-=t;

           G[e.to][e.rev].cap+=t;

       }

       res+=t*d[end];

   }

   return (double)res/n;

}

int main()

{

   int T;scanf("%d",&T);

   while(T--)

   {

       init();

       printf("%.6lf\n",solve());

   }

}