The Windy's （poj 3686 最小費用最大流 建圖經典）

Language: Default The Windy's Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 4662 Accepted: 1963 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

題意：n個訂單m個工作工廠中的房間，每個訂單隻能在同一個工廠中的房間全部完成，每個訂單在每個工廠中的房間完成的費用以矩陣給出，問完成所有訂單的最低平均費用為多少。

這題建圖确實想不出來，看了别人的講解，感覺太巧了！http://blog.csdn.net/weiguang_123/article/details/7881799

代碼：

#include <iostream>
#include <functional>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

#define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 1005;
const int MAXN = 5000;
const int MAXM = 300010;

struct Edge
{
    int to,next,cap,flow,cost;
}edge[MAXM];

int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N,n,m;

void init(int n)
{
    N=n;
    tol=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int cap,int cost)
{
    edge[tol].to=v;
    edge[tol].cap=cap;
    edge[tol].cost=cost;
    edge[tol].flow=0;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=0;
    edge[tol].cost=-cost;
    edge[tol].flow=0;
    edge[tol].next=head[v];
    head[v]=tol++;
}

bool spfa(int s,int t)
{
    queue<int>q;
    for (int i=0;i<N;i++)
    {
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v]=dis[u] + edge[i].cost;
                pre[v]=i;
                if (!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t]==-1) return false;
    else return true;
}

//傳回的是最大流，cost存的是最小費用
int minCostMaxflow(int s,int t,int &cost)
{
    int flow=0;
    cost=0;
    while (spfa(s,t))
    {
        int Min=INF;
        for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
        {
            if (Min > edge[i].cap-edge[i].flow)
                Min=edge[i].cap-edge[i].flow;
        }
        for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
        {
            edge[i].flow+=Min;
            edge[i^1].flow-=Min;
            cost+=edge[i].cost*Min;
        }
        flow+=Min;
    }
    return flow;
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
    int i,j,t,x;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        int S=0,T=n+n*m+1;
        init(n+n*m+2);
        for (i=1;i<=n;i++)
            addedge(0,i,1,0);
        for (i=0;i<m;i++)
            for (j=1;j<=n;j++)
                addedge(n+i*n+j,T,1,0);
        for (i=1;i<=n;i++)
        {
            for (j=0;j<m;j++)
            {
                scanf("%d",&x);
                for (int k=1;k<=n;k++)
                    addedge(i,n+j*n+k,1,k*x);
            }
        }
        int ans,cost;
        ans=minCostMaxflow(S,T,cost);
        printf("%.6f\n",1.0*cost/n);
    }
    return 0;
}