bzoj4349: 最小树形图

最小树形图模板题……

这种\(O(nm)\)的东西真的能考到么……

#include <bits/stdc++.h>

#define N 60

#define INF 1000000000

using namespace std;

int n, m, nn;

double ai[N], an[N], ci[][N][N], ans;

int bc[N];

int ini[N], vis[N], inc[N], inl[N];

int dfn;

int dfs(int t)

{

    vis[t] = dfn;

    if (vis[ini[t]] == vis[t])

        return ini[t];

    else if (vis[ini[t]])

        return ;

    else return dfs(ini[t]);

}

int main()

{

    scanf("%d", &n);

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

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

            ci[][i][j] = INF;

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

        scanf("%lf%d", &ai[i], &bc[i]), an[i] = ai[i], ci[][][i] = ai[i];

    scanf("%d", &m);

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

    {

        int a, b; double c;

        scanf("%d%d%lf", &a, &b, &c);

        if (a != b) ci[][a][b] = min(ci[][a][b], c);

        an[b] = min(an[b], c);

    }

    for (int i = ; i <= n; ++ i) ans += an[i] * (bc[i] - );

    int tmp = , wh = ; nn = n;

    while (wh)

    {

        wh = ;

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

        {

            double mn = INF;

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

                if (ci[tmp][j][i] < mn)

                    mn = ci[tmp][j][i], ini[i] = j;

        }

        for (int i = ; i <= nn; ++ i) vis[i] = ; vis[] = -;

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

            if (!vis[i])

            {

                dfn ++;

                int x = dfs(i);

                if (x)

                {

                    int tot = ;

                    wh = ;

                    for (int j = ; j <= nn; ++ j) inc[j] = ;

                    for (int j = ini[x]; j != x; j = ini[j]) inc[j] = ; inc[x] = ;

                    for (int j = ; j <= nn; ++ j) if (!inc[j]) inl[j] = tot ++; else ans += ci[tmp][ini[j]][j];

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

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

                            ci[!tmp][j][k] = INF;

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

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

                        {

                            if (!inc[j])

                            {

                                if (!inc[k])

                                    ci[!tmp][inl[j]][inl[k]] = min(ci[!tmp][inl[j]][inl[k]], ci[tmp][j][k]);

                                else

                                    ci[!tmp][inl[j]][tot] = min(ci[!tmp][inl[j]][tot], ci[tmp][j][k] - ci[tmp][ini[k]][k]);

                            }

                            else if (!inc[k])

                                    ci[!tmp][tot][inl[k]] = min(ci[!tmp][tot][inl[k]], ci[tmp][j][k]);

                        }

                    nn = tot;

                    break;

                }

            }

        if (!wh)

            for (int i = ; i <= nn; ++ i) ans += ci[tmp][ini[i]][i];

        else tmp ^= ;

    }

    printf("%.2lf", ans);

}