首页 > 代码库 > bzoj 1070 SCOI2007 修车

bzoj 1070 SCOI2007 修车

    好久没写网络流了……

    一开始以为是DP,没想出来,看题解发现是网络流。

    构图蛮有意思的。

    把维修人员拆成n个点,每个分点都与那n个点连边,费用为 c[i][j] * (1..n) 这是表示修了这个车后以后的人会增加这么些费用。

    上代码:

#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#define N 65#define M 15#define inf 0x7f7f7f7fusing namespace std;int n, m, S, T;int t[N][M], fa[N*M];int p[N*M], next[N*M*200], v[N*M*200], f[N*M*200], c[N*M*200], bnum = -1;int dis[N*M], vis[N*M];queue<int> q;void addbian(int x, int y, int fl, int co){    bnum++; next[bnum] = p[x]; p[x] = bnum;    v[bnum] = y; f[bnum] = fl; c[bnum] = co;    bnum++; next[bnum] = p[y]; p[y] = bnum;    v[bnum] = x; f[bnum] = 0; c[bnum] = -co;}bool bfs(){    for (int i = 1; i <= T; ++i) {dis[i] = inf; vis[i] = 0;}    vis[S] = 1; q.push(S); dis[S] = 0; fa[S] = -1;    while (!q.empty())    {        int j = q.front(); q.pop();        int k = p[j];        while (k != -1)        {            if (f[k] && dis[v[k]] > dis[j] + c[k])            {                fa[v[k]] = k;                dis[v[k]] = dis[j] + c[k];                if (!vis[v[k]])                {                    vis[v[k]] = 1;                    q.push(v[k]);                }            }            k = next[k];        }        vis[j] = 0;    }    if (dis[T] == inf) return false;    else return true;}void dinic(){    int ans = 0;    while (bfs())    {        int k = fa[T];        while (k != -1)        {            if (!f[k])                printf("now\n");            f[k] --;            ans += c[k];            f[k^1] ++;            k = fa[v[k^1]];        }    }    printf("%.2lf\n", (double)ans/(double)n);}int main(){    scanf("%d%d", &m, &n);    for (int i = 1; i <= n; ++i)        for (int j = 1; j <= m; ++j)            scanf("%d", &t[i][j]);    S = n*m+n+1; T = S+1;    for (int i = 1; i <= T; ++i) p[i] = -1;    for (int i = 1; i <= n*m; ++i) addbian(i, T, 1, 0);    for (int i = 1; i <= n; ++i) addbian(S, n*m+i, 1, 0);    for (int i = 1; i <= n; ++i)        for (int j = 1; j <= n*m; ++j)            addbian(n*m+i, j, 1, t[i][(j-1)/n+1]*(j%n+1));    dinic();    return 0;}

 

bzoj 1070 SCOI2007 修车