LYDSY 2330

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
int head[100010], next[500010], to[500010], len[500010], ecnt, n, k;
int que[10000010], dis[100010], vis[100010];
bool inq[100010];
inline void addEdge(int f, int t, int l)
{
    ecnt++;
    next[ecnt] = head[f];
    head[f] = ecnt;
    to[ecnt] = t;
    len[ecnt] = l;
}
bool spfa()
{
    dis[0] = 0, inq[0] = true, vis[0] = 1;
    int f, r;
    f = r = 0;
    que[r++] = 0;
    for (int x; f ^ r; inq[que[f++]] = false)
        for (int cur = head[x = que[f]]; cur; cur = next[cur])
            if (dis[to[cur]] < dis[x] + len[cur])
            {
                dis[to[cur]] = dis[x] + len[cur];
                if (++vis[to[cur]] > n || to[cur] == x) return false;
                if (!inq[to[cur]]) inq[que[r++] = to[cur]] = true;
            }
    return true;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0, x, a, b; i < k; i++)
    {
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) addEdge(a, b, 0), addEdge(b, a, 0);
        if (x == 2) addEdge(a, b, 1);
        if (x == 3) addEdge(b, a, 0);
        if (x == 4) addEdge(b, a, 1);
        if (x == 5) addEdge(a, b, 0);
    }
    for (int i = n; i; i--) addEdge(0, i, 1);
    long long ans = 0;
    if (!spfa())
        ans = -1;
    else
        for (int i = 1; i <= n; i++) ans += dis[i];
    printf("%lld", ans);
    return 0;
}