Big Christmas Tree

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 500010;

typedef long long LL;
typedef pair<LL, int> PLI;
#define INF 1LL<<61

int v, E;
LL h[N], e[N], ne[N], w[N], idx;
LL weight[N]; // 每个节点的权重
LL dist[N];
bool st[N];

void add(int a, int b, LL c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra() {
    for (int i = 0; i <= v; i ++ )

        dist[i] = INF;
    memset(st, false, sizeof st);
    dist[1] = 0;
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    PLI d;
    d.first = 0, d.second = 1;
    q.push(d);

    while (q.size()) {
        PLI t = q.top();
        q.pop();
        LL distance = t.first;
        int ver = t.second;

        if (st[ver])
            continue;
        st[ver] = true;

        for (LL i = h[ver]; i != -1; i = ne[i]) {

            LL j = e[i];

            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                d.first = dist[j], d.second = j;
                q.push(d);
            }
        }
    }

}

int main() {
    LL T;
    scanf("%lld", &T);

    while (T -- ) {
        memset(h, -1, sizeof h);
        idx = 0;
        scanf("%d%d", &v, &E);

        for (int i = 1; i <= v; i ++ )

            scanf("%lld", &weight[i]);

        while (E -- ) {
            int a, b;
            LL c;
            scanf("%d%d%lld", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }

        if (v == 0 || v == 1) {
            puts("0");
            continue;
        }

        dijkstra();
        LL sum = 0;
        bool flag = true;

        for (int i = 2; i <= v; i ++ ) {

            if (dist[i] == INF) {
                flag = false;
                break;
            }

            sum += weight[i] * dist[i];
        }

        if (flag)
            printf("%lld\n", sum);
        else
            puts("No Answer");
    }

    return 0;

}

Popular Cows

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010;

vector<int> V[N];  // v[i]存储的是编号为i的点的入度是哪些点
int n, m;
int a[N * 5], b[N * 5];
int dfn[N]; // 存的是每个点被搜索到的次序
int low[N]; //作为每个点在这颗树中的，最小的子树的根，每次保证最小.
int deep; //节点的编号
bool st[N]; // st[i]表示i节点在不在栈当中
int stack[N], cnt, w;
int sum; // 强连通分量的数量
int belong[N];
int outdgree[N];
int ans, pos;

void tarjan(int v) {
    int l = V[v].size();
    low[v] = dfn[v] = ++ deep;
    st[v] = true;
    stack[++ cnt] = v;

    for (int i = 0; i < l; i ++ ) {

        int ver = V[v][i];

        if (!dfn[ver]) {
            tarjan(ver);
            low[v] = min(low[ver], low[v]);
        } else if (st[ver])
            low[v] = min(dfn[ver], low[v]);
    }

    if (dfn[v] == low[v]) { //自己和子节点形成了强连通分量，或者只有自己孤身一人
        sum ++ ;

        do {
            w = stack[cnt -- ];
            st[w] = false;
            belong[w] = sum;
        } while (w != v);
    }
}

int main() {
    scanf("%d%d", &n, &m);

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

        scanf("%d%d", &a[i], &b[i]);
        V[b[i]].push_back(a[i]);
    }

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

        if (!dfn[i])  // i是新节点
            tarjan(i);

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

        if (belong[a[i]] != belong[b[i]])
            outdgree[belong[a[i]]] ++ ;

    for (int i = 1; i <= sum; i ++ )

        if (outdgree[i] == 0) {
            pos ++ ;
            ans = i;
        }

    int res = 0;

    if (pos > 1)
        puts("0");
    else if (pos == 0)
        puts("0");
    else {
        for (int i = 1; i <= n; i ++ )

            if (belong[i] == ans)
                res ++ ;
        printf("%d\n", res);
    }
}

Network of Schools

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int load[N][N];
int dfn[N], low[N], deep;
int stack[N], cnt;
bool st[N];
int belong[N], w, sum;
int in[N], out[N];

void tarjan(int v) {
    dfn[v] = low[v] = ++ deep;
    stack[++ cnt] = v;
    st[v] = true;

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

        if (!load[v][i])
            continue;

        if (!dfn[i]) {
            tarjan(i);
            low[v] = min(low[v], low[i]);
        } else if (st[i]) {
            low[v] = min(low[v], dfn[i]);
        }
    }

    if (dfn[v] == low[v]) {
        sum ++ ;

        do {
            w = stack[cnt -- ];
            st[w] = false;
            belong[w] = sum;
        } while (w != v);
    }
}

int main() {
    scanf("%d", &n);

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

        while (~scanf("%d", &m) && m)
            load[i][m] = 1;



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

        if (!dfn[i])
            tarjan(i);

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

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

            if (load[i][j] && belong[i] != belong[j]) {
                out[belong[i]] ++ ;
                in[belong[j]] ++ ;
            }

    int t1 = 0, t2 = 0;

    for (int i = 1; i <= sum; i ++ ) {

        if (!in[i])
            t1 ++ ;

        if (!out[i])
            t2 ++ ;
    }

    if (sum == 1)
        printf("1\n0\n");
    else
        printf("%d\n%d\n", t1, max(t1, t2));
    return 0;
}