bzoj1070 [SCOI2007]修车

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1070

【题解】

建图非常巧妙 需要仔细思考

我们考虑对第i个工人，倒数第j次修车建点，对于这里面每个点，连到T，流量1费用0表示只能用一次（废话）。

对于每辆车k，都可以连到这个点，流量1，费用t[k][i]*j（因为后面包括自己有j辆车在等）

S连到每辆车流量1费用0

# include <queue>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int m, n, t[66][66], S, T;
int id[66][66], idc[66], idx;

int head[M], nxt[M], to[M], tot=1, flow[M], w[M];
inline void add(int u, int v, int fl, int _w) {
    ++tot; nxt[tot] = head[u]; head[u] = tot;
    to[tot] = v; flow[tot] = fl; w[tot] = _w;
}
inline void adde(int u, int v, int fl, int _w) {
    add(u, v, fl, _w);
    add(v, u, 0, -_w);
}

// 第i个工人修第j辆车，是倒数第k个修的。 

namespace MCF {
    queue<int> q;
    int dis[M], pre[M];
    bool vis[M];
    inline bool spfa() {
        while(!q.empty()) q.pop();
        for (int i=1; i<=idx; ++i) vis[i] = 0, dis[i] = 1e9, pre[i] = 0;
        q.push(S); vis[S] = 1; dis[S] = 0;
        while(!q.empty()) {
            int top = q.front(); q.pop(); vis[top] = 0;
            for (int i=head[top]; i; i=nxt[i]) {
                if(flow[i] && dis[to[i]] > dis[top] + w[i]) {
                    dis[to[i]] = dis[top] + w[i];
                    pre[to[i]] = i;
                    if(!vis[to[i]]) {
                        vis[to[i]] = 1;
                        q.push(to[i]);
                    }
                }
            }
        }
        return dis[T] != 1e9;
    }
    inline int mcf() {
        int fl = 1e9, ans = 0;
        for (int i=pre[T]; i; i=pre[to[i^1]])
            fl = min(fl, flow[i]);
        for (int i=pre[T]; i; i=pre[to[i^1]]) {
            flow[i] -= fl;
            flow[i^1] += fl;
            ans += fl * w[i];
        }
        return ans;
    }
    inline int main() {
        int ret = 0;
        while(spfa()) ret += mcf();
        return ret;
    }    
}

int main() {
    cin >> m >> n;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j) scanf("%d", &t[i][j]);
    for (int i=1; i<=m; ++i)
        for (int j=1; j<=n; ++j) id[i][j] = ++idx; 
    for (int i=1; i<=n; ++i) idc[i] = ++idx;
    S = ++idx, T = ++idx; 
    for (int i=1; i<=m; ++i)
        for (int j=1; j<=n; ++j) { 
            adde(id[i][j], T, 1, 0); 
            for (int k=1; k<=n; ++k)
                adde(idc[k], id[i][j], 1, t[k][i]*j);
        }
    for (int i=1; i<=n; ++i) adde(S, idc[i], 1, 0);
    double ans = (double)MCF::main();
    ans /= (double)n;
    printf("%.2lf
", ans); 
    return 0;
}