神奇的0号药水题解

admin

[code=Cpp width=700px]#include <stdio.h>
#define M 1008

int f[1008], g[1008], p[1008];
int e[4000008][2], nx[4000008], head[1008], fre = 1;
int n;

int que[1008], tp, bt, in[1008];

void spfa()
{
        int u, k;

        bt = 0;
        for (tp = 0;tp < n;tp++)
        {
                que[tp] = tp;
                in[tp] = 1;
        }
        while (bt != tp)
        {
                u = que[bt++];
                bt %= M;
                for (k = head;k;k = nx[k])
                        if (f[ e[k][1] ] > f[ e[k][0] ] + f)
                        {
                                f[ e[k][1] ] = f[ e[k][0] ] + f;
                                if (in[ e[k][1] ] == 0)
                                {
                                        que[tp++] = e[k][1];
                                        tp %= M;
                                        in[ e[k][1] ] = 1;
                                }
                        }
        }
}

void ac(int u)
{
        int i, k;

        g = 0;
        for (i = 0;i < n;i++)
                for (k = head;k;k = nx[k])
                        if (f[ e[k][0] ] + f == f && e[k][1] == u)
                        {
                                ac(i);
                                ac(e[k][0]);
                                g += g[ e[k][0] ] * g;
                        }
        g /= 2;
        if (f == p)
                g++;
}

int main()
{
        freopen("syrup.in", "r", stdin);
        freopen("syrup.out", "w", stdout);
        int i, x, y, z;

        scanf("%d", &n);
        for (i = 0;i < n;i++)
        {
                scanf("%d", &f);
                p = f;
        }
        while (scanf("%d %d %d", &x, &y, &z) != EOF)
        {
                e[fre][0] = y; e[fre][1] = z; nx[fre] = head[x]; head[x] = fre++;
                e[fre][0] = x; e[fre][1] = z; nx[fre] = head[y]; head[y] = fre++;
        }
        spfa();
        ac(0);
        printf("%d %d\n", f[0], g[0]);
        return 0;
}
[/code]