(BZOJ) 1070: [SCOI2007]修车

http://www.lydsy.com/JudgeOnline/problem.php?id=1070

超神min cost max flow題。

可以想像說：假設第j個人先後修理車的順序是x_1, x_2, ......, x_t，那，a[x_1][j]的貢獻就是a[x_1][j] * t, a[x_2][j]就是a[x_2][j] * (t-1) ......

有了上面(?)的想法後，就可以寫flow了~

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define int long long
typedef pair<int,int> pii;

struct Flow
{
    static const int N = 100006;
    struct Edge
    {
        int to,cap,rev,cost;
        Edge(){}
        Edge(int _to,int _cap,int _rev,int _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,int cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int pre[N],pre_id[N];
    bool in_que[N];
    int dis[N];
    pii shooting_stars()
    {
        int flow=0,cost = 0;
        int INF = (1LL<<50);
        while (true)
        {
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            queue<int> que;
            que.push(s);
            dis[s] = 0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int i=0;G[t].size()>i;i++)
                {
                    Edge e=G[t][i];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = i;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            if (dis[t] == INF) break;
            int mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min( mn_flow, G[ pre[i] ][ pre_id[i] ].cap );
            }
            flow += mn_flow;
            cost += mn_flow * dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[ i ][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} sagiri;

const int N = 66;

int a[N][N];

int32_t main ()
{
    int m,n;
    scanf("%lld %lld",&m,&n);
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            scanf("%lld",&a[i][j]);
        }
    }
    int s=0,t = 100002;
    sagiri.init(t,s,t);
    for (int i=1;n>=i;i++)
    {
        sagiri.add_edge(i,t,1,0);
    }
    int now = n+1;
    for (int i=1;m>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            int tmp=now;
            now++;
            sagiri.add_edge(s,tmp,1,0);
            for (int k=1;n>=k;k++)
            {
                //i-th person fix k-th car at time j
                int _=now;
                sagiri.add_edge(tmp,_,1,a[k][i]*j);
                now++;
                sagiri.add_edge(_,k,1,0);
            }
        }
    }
    pii ret = sagiri.shooting_stars();
    printf("%.2f\n",ret.second*1.0/n);
}