[SCOI 2007] 修车

[题目链接]

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

[算法]

首先 ， 我们发现 ， 在倒数第i个修车会对答案产生i * k的贡献

将每辆车建一个点 ， 每名技术人员建n个点 ，将车与技术人员连边 ， 第i个技术人员的第j个点与第k辆车连边表示k是i修的倒数第j辆车

然后在这张图上求最小费用最大流 ， 即可

时间复杂度 ： O(Costflow(NM , N ^ 2M))

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 550

const int INF = 1e9;

struct edge

{

        int to , w , cost , nxt;

} e[MAXN * MAXN * ];

int n , m , tot , ans , S , T;

int a[MAXN][MAXN];

int head[MAXN * MAXN] , dist[MAXN * MAXN] , pre[MAXN * MAXN] , incf[MAXN * MAXN];

bool inq[MAXN * MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void addedge(int u , int v , int w , int cost)

{

        ++tot;

        e[tot] = (edge){v , w , cost , head[u]};

        head[u] = tot;

        ++tot;

        e[tot] = (edge){u ,  , -cost , head[v]};

        head[v] = tot;

}

inline bool spfa()

{

        int l , r;

        static int q[MAXN * MAXN];

        for (int i = ; i <= T; i++)

        {

                pre[i] = ;

                dist[i] = INF;

                incf[i] = INF;

                inq[i] = false;

        }

        q[l = r = ] = S;

        dist[S] = ;

        inq[S] = true;

        while (l <= r)

        {

                int cur = q[l++];

                inq[cur] = false;

                for (int i = head[cur]; i; i = e[i].nxt)

                {

                        int v = e[i].to , w = e[i].w , cost = e[i].cost;

                        if (w >  && dist[cur] + cost < dist[v])

                        {

                                dist[v] = dist[cur] + cost;

                                incf[v] = min(incf[cur] , w);

                                pre[v] = i;

                                if (!inq[v])

                                {

                                        q[++r] = v;

                                        inq[v] = true;

                                }

                        }

                }

        }

        if (dist[T] != INF) return true;

        else return false;

}

inline void update()

{

        int now = T , pos;

        while (now != S)

        {

                pos = pre[now];

                e[pos].w -= incf[T];

                e[pos ^ ].w += incf[T];

                now = e[pos ^ ].to;

        }

        ans += dist[T] * incf[T];

}

int main()

{

        read(m); read(n);

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

        {

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

                {

                        read(a[i][j]);

                }

        }

        tot = ;

        S = n * m + n +  , T = S + ;

        for (int i = ; i <= n; i++) addedge(S , i ,  , );

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

        {

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

                {

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

                        {

                                addedge(i , n + (j - ) * n + k ,  , a[i][j] * k);

                        }

                }

        }

        for (int i = ; i <= n * m; i++) addedge(i + n , T ,  , );

        while (spfa()) update();

        printf("%.2lf\n" , 1.0 * ans / n);

        return ;

}