头像

yuanwen

ENWOM




离线:1小时前


活动打卡代码 AcWing 1183. 电力

yuanwen
13小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = 30010;

int h[N], e[M], ne[M], idx, n, m, cnt;

int dfn[N], low[N], timestamp, root, cut[N];

void init() {
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(h, -1, sizeof h);
    memset(cut, 0, sizeof cut);
    timestamp = 0;
    cnt = -1;
    idx = 0;
}

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

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) cut[u]++;
        } else low[u] = min(low[u], dfn[j]);
    }
    if (u != root) cut[u]++;
}

int main() {
    while (cin >> n >> m, n || m) {
        init();
        while (m--) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        for (int i = 0; i < n; i++)
            if (!dfn[i]) {
                cnt++;
                root = i;
                tarjan(i);
            }
        int res = 0;
        for (int i = 0; i < n; i++) res = max(res, cut[i]);
        cout << res + cnt << endl;
    }
    return 0;
}


活动打卡代码 AcWing 395. 冗余路径

yuanwen
15小时前
#include <iostream>

using namespace std;

const int N = 5010, M = 2 * N;

int h[N], e[M], ne[M], n, m, idx = 1;

int dfn[N], low[N], id[N], dcc_cnt, timestamp, deg[N];

bool bridge[M];

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

void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++timestamp;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (low[j] > dfn[u]) bridge[i] = bridge[i ^ 1] = true;
        } else if (i != (in_edge ^ 1)) low[u] = min(low[u], dfn[j]);
    }
}

void dfs(int u) {
    id[u] = dcc_cnt;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (id[j] || bridge[i]) continue;
        dfs(j);
    }
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    tarjan(1, -1);
    for (int i = 1; i <= n; i++)
        if (!id[i]) dcc_cnt++, dfs(i);
    for (int i = 2; i <= idx; i++) {
        int x = e[i], y = e[i ^ 1];
        if (id[x] != id[y]) deg[id[y]]++;
    }
    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i++)
        if (deg[i] == 1) cnt++;
    cout << (cnt + 1) / 2 << endl;
    return 0;
}


活动打卡代码 AcWing 368. 银河

yuanwen
1天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 5, M = 6 * N;

typedef long long LL;

int hr[N], e[M], ne[M], w[M], idx, hc[N];

int stk[N], scc_cnt, top, timestamp, dfn[N], low[N], id[N], sz[N];

int n, m, dist[N];

bool in_stk[N], st[N];

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

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = hr[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = false;
            sz[scc_cnt]++;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

void bfs() {
    memset(dist, 0xcf, sizeof dist);
    dist[scc_cnt] = 0;
    queue<int> q;
    q.push(scc_cnt);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = hc[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
}

int main() {
    memset(hr, -1, sizeof hr);
    memset(hc, -1, sizeof hc);
    cin >> n >> m;
    while (m--) {
        int a, b, k;
        scanf("%d%d%d", &k, &a, &b);
        if (k == 1) add(hr, a, b, 0), add(hr, b, a, 0);
        else if (k == 2) add(hr, a, b, 1);
        else if (k == 3) add(hr, b, a, 0);
        else if (k == 4) add(hr, b, a, 1);
        else add(hr, a, b, 0);
    }
    for (int i = 1; i <= n; i++) add(hr, 0, i, 1);
    tarjan(0);
    bool flag = false;
    for (int u = 0; u <= n; u++) {
        for (int i = hr[u]; ~i; i = ne[i]) {
            int j = e[i], a = id[u], b = id[j];
            if (a == b && w[i]) {
                flag = true;
                break;
            }
            if (a != b) add(hc, a, b, w[i]);
        }
    }
    if (flag) puts("-1");
    else {
        bfs();
        LL res = 0;
        for (int i = 1; i < scc_cnt; i++) res += sz[i] * dist[i];
        cout << res << endl;
    }
    return 0;
}



yuanwen
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 1e5 + 5, M = 2e6 + 5;

typedef long long LL;

int hr[N], hc[N], e[M], ne[M], idx;

int scc_cnt, sz[N], dfn[N], low[N], stk[N], top, timestamp, id[N];

int f[N], g[N], n, m, mod;

bool in_stk[N];

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

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = hr[u]; i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        int y;
        scc_cnt++;
        do {
            y = stk[top--];
            sz[scc_cnt]++;
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main() {
    cin >> n >> m >> mod;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(hr, a, b);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    unordered_set<LL> edge;
    for (int u = 1; u <= n; u++) {
        for (int i = hr[u]; i; i = ne[i]) {
            int a = id[u], b = id[e[i]];
            if (a == b) continue;
            LL hash = a * 1000000ll + b;
            if (!edge.count(hash)) {
                edge.insert(hash);
                add(hc, a, b);
            }
        }
    }
    for (int i = scc_cnt; i; i--) {
        if (!f[i]) f[i] = sz[i], g[i] = 1;
        for (int j = hc[i]; j; j = ne[j]) {
            int t = e[j];
            if (f[t] < f[i] + sz[t]) {
                f[t] = f[i] + sz[t];
                g[t] = g[i];
            } else if (f[t] == f[i] + sz[t]) g[t] = (g[t] + g[i]) % mod;
        }
    }
    int res = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (f[i] > res) res = f[i], sum = g[i];
        else if (f[i] == res) sum = (sum + g[i]) % mod;
    }
    cout << res << endl << sum << endl;
    return 0;
}


活动打卡代码 AcWing 367. 学校网络

yuanwen
3天前
#include <iostream>

using namespace std;

const int N = 110;

int n, t, dfn[N], low[N], scc_cnt, din[N], dout[N], top, timestamp, id[N], stk[N];

bool g[N][N], in_stk[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = 1; i <= n; i++) {
        if (!g[u][i]) continue;
        if (!dfn[i]) {
            tarjan(i);
            low[u] = min(low[u], low[i]);
        } else if (in_stk[i]) low[u] = min(low[u], dfn[i]);
    }
    if (dfn[u] == low[u]) {
        int y;
        scc_cnt++;
        do {
            y = stk[top--];
            id[y] = scc_cnt;
            in_stk[y] = false;
        } while (y != u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        while (cin >> t, t) g[i][t] = true;
    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 (g[i][j]) {
                int a = id[i], b = id[j];
                if (a != b)
                    dout[a]++, din[b]++;
            }
    int P = 0, Q = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) P++;
        if (!dout[i]) Q++;
    }
    cout << P << endl;
    if (scc_cnt == 1) puts("0");
    else cout << max(P, Q) << endl;
    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛

yuanwen
3天前
#include <iostream>

using namespace std;

const int N = 10010, M = 5 * N;

int n, m, h[N], e[M], ne[M], idx;

int dfn[N], low[N], timestamp;

int stk[N], top, id[N], scc_cnt, sz[N], deg[N];

bool in_stk[N];

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

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int y;
        do {
            sz[scc_cnt]++;
            y = stk[top--]; 
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);

    }
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) 
            tarjan(i);
    for (int u = 1; u <= n; u++) {
        for (int i = h[u]; i; i = ne[i]) {
            int j = e[i];
            int a = id[u], b = id[j];
            if (a != b) deg[a]++;
        }
    }
    int sum = 0;
    for (int i = 1, t = 0; i <= scc_cnt; i++) {
        if (!deg[i]) {
            if (t == 1) {
                sum = 0;
                break;
            }
            sum = sz[i], t = 1;
        }
    }
    cout << sum << endl;
    return 0;
}


活动打卡代码 AcWing 352. 闇の連鎖

yuanwen
4天前
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010, M = 2 * N;

int h[N], e[M], ne[M], idx, n, m;

int depth[N], anc[N][17], d[N], ans;

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

void bfs() {
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;   
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                anc[j][0] = t;
                q.push(j);
                for (int k = 1; k <= 16 && anc[j][k - 1]; k++) 
                    anc[j][k] = anc[anc[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int h = depth[a] - depth[b];
    for (int i = 0; h; i++) {
        if (h & 1) a = anc[a][i];
        h >>= 1;
    }
    if (a == b) return a;
    for (int i = 16; i >= 0; i--) 
        if (anc[a][i] != anc[b][i]) 
            a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}

int dfs(int u, int parent) {
    int res = d[u];
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (j == parent) continue;
        int s = dfs(j, u);
        res += s;
        if (s == 0) ans += m;
        else if (s == 1) ans++;
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    bfs();
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        d[a]++, d[b]++, d[p] -= 2;
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 356. 次小生成树

yuanwen
4天前
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3 * N, INF = 0x3f3f3f3f;

typedef long long LL;

struct Edge {
    int a, b, w;
    bool used;

    bool operator<(const Edge &e) const {
        return w < e.w;
    }
} edges[M];

int h[N], e[M], ne[M], w[M], idx, n, m;

int d1[N][17], d2[N][17], p[N], fa[N][17], depth[N], q[N];

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

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

LL kruskal() {
    sort(edges, edges + m);
    LL res = 0;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].a), b = find(edges[i].b), c = edges[i].w;
        if (a != b) {
            res += c;
            p[a] = b;
            edges[i].used = true;
        }
    }
    return res;
}

void build() {
    for (int i = 0; i < m; i++) {
        if (edges[i].used) {
            int a = edges[i].a, b = edges[i].b, c = edges[i].w;
            add(a, b, c), add(b, a, c);
        }
    }
}

void bfs() {
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for (int k = 1; k <= 16; k++) {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for (int u = 0; u < 4; u++) {
                        int d = distance[u];
                        if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }

            }
        }
    }
}

int lca(int a, int b, int w) {
    static int distance[N * 2];
    int cnt = 0;
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b]) {
            distance[cnt++] = d1[a][k];
            distance[cnt++] = d2[a][k];
            a = fa[a][k];
        }
    if (a != b) {
        for (int k = 16; k >= 0; k--)
            if (fa[a][k] != fa[b][k]) {
                distance[cnt++] = d1[a][k];
                distance[cnt++] = d2[a][k];
                distance[cnt++] = d1[b][k];
                distance[cnt++] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        distance[cnt++] = d1[a][0];
        distance[cnt++] = d1[b][0];
    }
    int dist1 = -INF, dist2 = -INF;
    for (int i = 0; i < cnt; i++) {
        int d = distance[i];
        if (d > dist1) dist2 = dist1, dist1 = d;
        else if (d != dist1 && d > dist2) dist2 = d;
    }
    if (w > dist1) return w - dist1;
    if (w > dist2) return w - dist2;
    return INF;
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    LL sum = kruskal();
    build();
    bfs();
    LL res = 1e18;
    for (int i = 0; i < m; i++) {
        if (!edges[i].used) {
            int a = edges[i].a, b = edges[i].b, c = edges[i].w;
            res = min(res, lca(a, b, c) + sum);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1171. 距离

yuanwen
4天前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 20010, M = 2 * N;

typedef pair<int, int> PII;

int h[N], e[M], ne[M], w[M], idx, n, m;

int res[N], p[N], dist[N], st[N];

vector<PII> query[N]; // first 表示查询相关的另一个点,second表示查询的编号

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

void dfs(int u, int fa) {
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

void tarjan(int u) {
    st[u] = 1;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        tarjan(j);
        p[j] = u;
    }
    for (auto t : query[u]) {
        int ver = t.first, id = t.second;
        if (st[ver] == 2) {
            int anc = find(ver);
            res[id] = dist[u] + dist[ver] - 2 * dist[anc];
        }
    }
    st[u] = 2;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        if (x != y) query[x].push_back({y, i}), query[y].push_back({x, i});
    }
    for (int i = 1; i <= n; i++) p[i] = i;
    dfs(1, -1);
    tarjan(1);
    for (int i = 0; i < m; i++) cout << res[i] << endl;
    return 0;
}



活动打卡代码 AcWing 1172. 祖孙询问

yuanwen
4天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 40010, M = 2 * N;

int h[N], e[M], ne[M], idx, n, m, root;

int depth[N], fa[N][16];

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

void bfs() {
    memset(depth, 0x3f, sizeof depth);
    depth[root] = 1, depth[0] = 0;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 15 && fa[j][k - 1]; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k--) 
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k--)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    bfs();
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        int p = lca(x, y);
        if (p == x) puts("1");
        else if (p == y) puts("2");
        else puts("0");
    }
    return 0;
}