头像

Initialize.

在AFO的边缘挣扎


访客:6177

离线:9个月前


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

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, e, num, top, col;
int head[MAXN], dfn[MAXN], low[MAXN];
int Stack[MAXN], inSCC[MAXN], inDeg[MAXN], outDeg[MAXN];
bool inStack[MAXN];

struct Edge {
    int from, to, nxt;
} edge[MAXN * MAXN];

void addedge(int from, int to)
{
    edge[++e].to = to;
    edge[e].from = from;
    edge[e].nxt = head[from];
    head[from] = e;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++num;
    Stack[++top] = u;
    inStack[u] = true;
    for (int i = head[u];i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        inSCC[u] = ++col;
        while (Stack[top] != u) {
            inStack[Stack[top]] = false;
            inSCC[Stack[top--]] = col;
        }
        inStack[Stack[top--]] = false;
    }
}

void init()
{
    scanf("%d", &n);
    for (int i = 1;i <= n;++i) {
        int vi;
        while (~scanf("%d", &vi) && vi) {
            addedge(i, vi);
        }
    }
}

void work()
{
    for (int i = 1;i <= n;++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = 1;i <= e;++i) {
        int ui = edge[i].from;
        int vi = edge[i].to;
        if (inSCC[ui] != inSCC[vi]) {
            outDeg[inSCC[ui]]++;
            inDeg[inSCC[vi]]++;
        }
    }
    int zeroIN = 0, zeroOUT = 0;
    for (int i = 1;i <= col;++i) {
        zeroIN += (inDeg[i] == 0);
        zeroOUT += (outDeg[i] == 0);
    }
    printf("%d\n%d", zeroIN, col == 1 ? 0 : max(zeroIN, zeroOUT));
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 364. 网络

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005, MAXM = MAXN * 2;

int n, m, e, t, q, cnt, num, bdg, caseID;
int head[MAXN], node[MAXN], dfn[MAXN], low[MAXN], inDCC[MAXN];
int dep[MAXN], fa[MAXN][20], lg[MAXN], back[MAXN];
bool isBridge[MAXM * 2], flag[MAXM * 2];

struct Edge {
    int to, nxt;
} edge[MAXM * 2];

struct Path {
    int to, nxt;
} path[MAXM * 2];

template<typename T> void qread(T &sum)
{
    sum = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        sum = (sum << 1) + (sum << 3) + ch - '0';
        ch = getchar();
    }
}

inline void addedge(int from, int to)
{
    edge[e].to = to;
    edge[e].nxt = head[from];
    head[from] = e++;
}

inline void addpath(int from, int to)
{
    path[t].to = to;
    path[t].nxt = node[from];
    node[from] = t++;
}

void tarjan(int u, int inEdge)
{
    dfn[u] = low[u] = ++num;
    for (int i = head[u];~i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                isBridge[i] = isBridge[i ^ 1] = true;
                bdg++;
            }
        } else if (i != (inEdge ^ 1)) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int f)
{
    inDCC[u] = cnt;
    for (int i = head[u];~i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == f || isBridge[i] || inDCC[v]) continue;
        dfs(v, u);
    }
}

void prepare(int u, int f)
{
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (int i = 1;i <= lg[dep[u]];++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = node[u];~i;i = path[i].nxt) {
        int v = path[i].to;
        if (v == f) continue;
        back[v] = i ^ 1;
        prepare(v, u);
    }
}

int LCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] != dep[v]) {
        u = fa[u][lg[dep[u] - dep[v]]];
    }
    if (u == v) return u;
    for (int i = lg[dep[u]];i >= 0;--i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void jump(int st, int ed, int &ct)
{
    while (st != ed) {
        if (flag[back[st]] == false) {
            ct++;
            flag[back[st]] = true;
        }
        st = fa[st][0];
    }
}

void init()
{
    e = 0;
    memset(head, -1, sizeof head);
    for (int i = 1;i <= m;++i) {
        int ui, vi;
        qread(ui), qread(vi);
        addedge(ui, vi);
        addedge(vi, ui);
    }
    scanf("%d", &q);
}

void work()
{
    printf("Case %d:\n", ++caseID);
    //求原图中的割边。
    num = bdg = 0;
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(isBridge, false, sizeof isBridge);
    tarjan(1, -1);
    //染色,求原图中各个边双连通分量。
    cnt = 0;
    memset(inDCC, 0, sizeof inDCC);
    for (int i = 1;i <= n;++i) {
        if (!inDCC[i]) {
            cnt++;
            dfs(i, 0);
        }
    }
    //缩点。
    t = 0;
    memset(node, -1, sizeof node);
    for (int i = 0;i < e;++i) {
        if (isBridge[i]) {
            int ui = inDCC[edge[i].to];
            int vi = inDCC[edge[i ^ 1].to];
            addpath(ui, vi);
        }
    }
    //用倍增LCA前的预处理。
    memset(dep, 0, sizeof dep);
    memset(fa, 0, sizeof fa);
    memset(back, 0, sizeof back);
    back[1] = -1;
    prepare(1, 0);
    //处理每个询问。
    memset(flag, false, sizeof flag);
    for (int i = 1;i <= q;++i) {
        int ui, vi;
        scanf("%d%d", &ui, &vi);
        if (inDCC[ui] != inDCC[vi]) {
            int tmp = 0, lca = LCA(inDCC[ui], inDCC[vi]);
            jump(inDCC[ui], lca, tmp);
            jump(inDCC[vi], lca, tmp);
            bdg -= tmp;
        }
        printf("%d\n", bdg);
    }
    putchar('\n');
}

int main()
{
    lg[0] = -1;
    for (int i = 1;i < MAXN;++i) lg[i] = lg[i >> 1] + 1;
    while (~scanf("%d%d", &n, &m) && n && m) {
        init();
        work();
    }
    return 0;
}


活动打卡代码 AcWing 363. B城

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005, MAXM = 500005;

int n, m, e, num, col, root;
int head[MAXN], low[MAXN], dfn[MAXN], size[MAXN];
long long ans[MAXN];

struct Edge {
    int to, nxt;
} edge[MAXM << 1];

template<typename T> void qread(T &sum)
{
    sum = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        sum = (sum << 1) + (sum << 3) + ch - '0';
        ch = getchar();
    }
}

inline void addedge(int from, int to)
{
    edge[++e].to = to;
    edge[e].nxt = head[from];
    head[from] = e;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++num;
    size[u] = 1;
    bool flag = false;
    int cnt = 0, sum = 0;
    for (int i = head[u];i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            size[u] += size[v];
            if (low[v] >= dfn[u]) {
                cnt++;
                ans[u] += (long long)size[v] * (n - size[v]);
                sum += size[v];
                if (u != 1 || cnt >= 2) flag = true;
            }
        } else low[u] = min(low[u], dfn[v]);
    }
    if (flag) {
        ans[u] += (long long)(sum + 1) * (n - sum - 1) + (n - 1);
    } else ans[u] = 2 * (n - 1);
}

void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= m;++i) {
        int ui, vi;
        qread(ui), qread(vi);
        addedge(ui, vi);
        addedge(vi, ui);
    }
}

void work()
{
    tarjan(1);
    for (int i = 1;i <= n;++i) {
        printf("%lld\n", ans[i]);
    }
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 361. 观光奶牛

Initialize.
9个月前

注意边权是实数,与边权相关的地方都要用double。

记录每个节点入队次数来判断是否有负环:447ms

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1E-6;
const int MAXN = 1005, MAXM = 5005;

int n, m, e;
int head[MAXN], f[MAXN], cnt[MAXN];
double dist[MAXN];
bool inQueue[MAXN];
queue<int> q;

struct Path {
    int from, to, wgt;
} path[MAXM];

struct Edge {
    int to, nxt;
    double wgt;
} edge[MAXM];

inline void addedge(int from, int to, double wgt)
{
    edge[++e].to = to;
    edge[e].wgt = wgt;
    edge[e].nxt = head[from];
    head[from] = e;
}

bool check(double lim)
{
    e = 0;
    memset(head, 0, sizeof head);
    memset(dist, 0, sizeof dist);
    for (int i = 1;i <= m;++i) {
        addedge(path[i].from, path[i].to, lim * path[i].wgt - f[path[i].from]);
    }
    while (!q.empty()) q.pop();
    for (int i = 1;i <= n;++i) {
        cnt[i] = 1;
        inQueue[i] = true;
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        for (int i = head[u];i;i = edge[i].nxt) {
            int v = edge[i].to;
            double w = edge[i].wgt;
            if (dist[v] > dist[u] + w) {
                if (++cnt[v] >= n) {
                    return true;
                }
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return false;
}

void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;++i) scanf("%d", &f[i]);
    for (int i = 1;i <= m;++i) {
        scanf("%d%d%d", &path[i].from, &path[i].to, &path[i].wgt);
    }
}

void work()
{
    double l = 0, r = 1000;
    while (r - l >= EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", l);
}

int main()
{
    init();
    work();
    return 0;
}

另一种判负环方法:41ms

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1E-6;
const int MAXN = 1005, MAXM = 5005;

int n, m, e;
int head[MAXN], f[MAXN];
bool flag;
bool vis[MAXN];
double dist[MAXN];

struct Path {
    int from, to, wgt;
} path[MAXM];

struct Edge {
    int to, nxt;
    double wgt;
} edge[MAXM];

void addedge(int from, int to, double wgt)
{
    edge[++e].to = to;
    edge[e].wgt = wgt;
    edge[e].nxt = head[from];
    head[from] = e;
}

void build(double lim)
{
    e = 0;
    memset(head, 0, sizeof head);
    memset(dist, 0, sizeof dist);
    memset(vis, false, sizeof vis);
    for (int i = 1;i <= m;++i) {
        addedge(path[i].from, path[i].to, lim * path[i].wgt - f[path[i].from]);
    }
}

void dfs(int u)
{
    vis[u] = true;
    for (int i = head[u];i;i = edge[i].nxt) {
        int v = edge[i].to;
        double w = edge[i].wgt;
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            if (vis[v] || flag) {
                flag = true;
                return;
            }
            dfs(v);
        }
    }
    vis[u] = false;
}

bool check(double lim)
{
    build(lim);
    flag = false;
    for (int i = 1;i <= n;++i) {
        dfs(i);
        if (flag) return true;
    }
    return false;
}

void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;++i) scanf("%d", &f[i]);
    for (int i = 1;i <= m;++i) {
        scanf("%d%d%d", &path[i].from, &path[i].to, &path[i].wgt);
    }
}

void work()
{
    double l = 0, r = 1000;
    while (r - l >= EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", l);
}

int main()
{
    init();
    work();
    return 0;
}

这个SPFA基于DFS。

其原理是:由于dis数组初值全部为零,所以如果从根节点到当前节点u的路径的边权总和为正,那么该节点不可能更新其它任何节点。

而当且仅当这条路径上的边权总和为负数时,它可以去更新其他节点的dis值。这条路径有可能成为一个负环的一部分。如果这条负链扩展到了组成自己的节点,就说明图中存在负环。



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

Initialize.
9个月前

add or not.png

我们发现,在最后执行DFS后,$cnt$为0的节点可能有三种情况:

  • 不是根节点,所有子节点的$cnt$值全为零;
  • 不是根节点,存在子节点的$cnt$值不为零;
  • 是根节点。

对于第一种节点,也就是图中最后两层中标记为0的节点,每个可以对答案产生$m$的贡献;
对于第二种节点,也就是图中的节点$R$,也可以对答案产生$m$的贡献;
对于第三种节点,也就是图中的节点$R’$,我们不能考虑其对答案的贡献,因为它没有连向其父节点的边了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005, MAXM = 300005;

int n, m, e, ans;
int head[MAXN], cnt[MAXN], fa[MAXN][20], dep[MAXN], lg[MAXN];

struct Edge {
    int to, nxt;
} edge[MAXM << 1];

template<typename T> void qread(T &sum)
{
    sum = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        sum = (sum << 1) + (sum << 3) + ch - '0';
        ch = getchar();
    }
}

inline void addedge(int from, int to)
{
    edge[++e].to = to;
    edge[e].nxt = head[from];
    head[from] = e;
}

void prepare(int u, int f)
{
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (int i = 1;i <= lg[dep[u]];++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = head[u];i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == f) continue;
        prepare(v, u);
    }
}

int LCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] != dep[v]) {
        u = fa[u][lg[dep[u] - dep[v]]];
    }
    if (u == v) return u;
    for (int i = lg[dep[u]];i >= 0;--i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void getANS(int u, int f)
{
    for (int i = head[u];i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == f) continue;
        getANS(v, u);
        cnt[u] += cnt[v];
    }
    if (cnt[u] == 0) ans += m;
    else if (cnt[u] == 1) ans += 1;
}

void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n - 1;++i) {
        int ui, vi;
        qread(ui), qread(vi);
        addedge(ui, vi);
        addedge(vi, ui);
    }
    lg[0] = -1;
    for (int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
}

void work()
{
    prepare(1, 0);
    for (int i = 1;i <= m;++i) {
        int ui, vi;
        qread(ui), qread(vi);
        cnt[ui]++, cnt[vi]++, cnt[LCA(ui, vi)] -= 2;
    }
    getANS(1, 0);
    for (int i = head[1];i;i = edge[i].nxt) {
        int v = edge[i].to;
        if (cnt[v]) {
            ans -= m;
            break;
        }
    }
    printf("%d", ans);
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 350. 巡逻

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

typedef pair<int, int> PII;

int n, k, e, ans;
int head[MAXN], D[MAXN], F[MAXN], preNode[MAXN], preEdge[MAXN];
bool vis[MAXN];

struct Edge {
    int to, nxt, wgt;
} edge[MAXN << 1];

void addedge(int from, int to, int wgt)
{
    edge[e].to = to;
    edge[e].wgt = wgt;
    edge[e].nxt = head[from];
    head[from] = e++;
}

void BFS()
{
    int dis1 = 0, pos1 = 0;
    queue<pair<int, int> > q;
    q.push({1, 0});
    while (!q.empty()) {
        PII u = q.front();
        q.pop();
        if (vis[u.first]) continue;
        vis[u.first] = true;
        if (u.second > dis1) {
            dis1 = u.second;
            pos1 = u.first;
        }
        for (int i = head[u.first];~i;i = edge[i].nxt) {
            int v = edge[i].to;
            int w = edge[i].wgt;
            if (vis[v]) continue;
            q.push({v, u.second + w});
        }
    }
    memset(vis, false, sizeof vis);
    int dis2 = 0, pos2 = pos1;
    q.push({pos2, 0});
    while (!q.empty()) {
        PII u = q.front();
        q.pop();
        if (vis[u.first]) continue;
        vis[u.first] = true;
        if (u.second > dis2) {
            dis2 = u.second;
            pos2 = u.first;
        }
        for (int i = head[u.first];~i;i = edge[i].nxt) {
            int v = edge[i].to;
            int w = edge[i].wgt;
            if (vis[v]) continue;
            preNode[v] = u.first;
            preEdge[v] = i;
            q.push({v, u.second + w});
        }
    }
    int cur = pos2;
    while (preNode[cur]) {
        edge[preEdge[cur]].wgt = -1;
        edge[preEdge[cur] ^ 1].wgt = -1;
        cur = preNode[cur];
    }
    ans = ans - dis2 + 1;
}

void DP(int u, int f)
{
    bool isLeave = true;
    for (int i = head[u];~i;i = edge[i].nxt) {
        int v = edge[i].to;
        int w = edge[i].wgt;
        if (v == f) continue;
        isLeave = false;
        DP(v, u);
        F[u] = max(F[u], D[u] + D[v] + w);
        D[u] = max(D[u], D[v] + w);
    }
    if (isLeave) D[u] = 0;
}

void init()
{
    scanf("%d%d", &n, &k);
    memset(head, -1, sizeof head);
    memset(D, -0x3f, sizeof D);
    memset(F, -0x3f, sizeof F);
    for (int i = 1;i < n;++i) {
        int ui, vi;
        scanf("%d%d", &ui, &vi);
        addedge(ui, vi, 1);
        addedge(vi, ui, 1);
    }
    ans = 2 * (n - 1);
}

void work()
{
    BFS();
    if (k == 2) {
        DP(1, 0);
        int diam = -0x3f3f3f3f;
        for (int i = 1;i <= n;++i) {
            diam = max(diam, F[i]);
        }
        ans = ans - diam + 1;
    }
    printf("%d", ans);
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 349. 黑暗城堡

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005, P = 2147483647;

int n, m, ans = 1;
int path[MAXN][MAXN];
bool inMST[MAXN];

struct Room {
    int ID, dist;
    friend bool operator <(const Room &a, const Room &b) {
        return a.dist < b.dist;
    }
} room[MAXN];

struct Node {
    int pos, dis;
    Node(int _pos = 0, int _dis = 0) {
        pos = _pos, dis = _dis;
    }
    friend bool operator <(const Node &a, const Node &b) {
        return a.dis > b.dis;
    }
};

void prepare()
{
    priority_queue<Node> pq;
    pq.push(Node(1, 0));
    room[1].dist = 0;
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int u = cur.pos;
        if (room[u].dist != cur.dis) continue;
        for (int i = 1;i <= n;++i) {
            if (i != u && path[i][u] != 0x3f3f3f3f) {
                if (room[i].dist > room[u].dist + path[i][u]) {
                    room[i].dist = room[u].dist + path[i][u];
                    pq.push(Node(i, room[i].dist));
                }
            }
        }
    }
    sort(room + 1, room + n + 1);
}

void getMST()
{
    inMST[room[1].ID] = true;
    for (int i = 2;i <= n;++i) {
        int cnt = 0;
        for (int j = 1;j <= n;++j) {
            if (inMST[room[j].ID]) {
                cnt += (room[j].dist + path[room[j].ID][room[i].ID] == room[i].dist);
            }
        }
        inMST[room[i].ID] = true;
        ans = ((long long)(ans % P) * (cnt % P)) % P;
    }
}

void init()
{
    scanf("%d%d", &n, &m);
    memset(path, 0x3f, sizeof path);
    for (int i = 1;i <= n;++i) path[i][i] = 0;
    for (int i = 1;i <= m;++i) {
        int ui, vi, wi;
        scanf("%d%d%d", &ui, &vi, &wi);
        path[ui][vi] = path[vi][ui] = min(path[ui][vi], wi);
    }
    for (int i = 1;i <= n;++i) {
        room[i].ID = i;
        room[i].dist = 0x3f3f3f3f;
    }
}

void work()
{
    prepare();
    getMST();
    printf("%d", ans % P);
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 347. 野餐规划

Initialize.
9个月前

只要思路足够清晰,看完题解后你也可以做到一遍AC$\text{Q}\omega \text{Q}$

写法应该有些复杂,仅供参考。

#include <map>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, e, s, root/*公园节点*/, tot/*节点个数*/, cnt/*连通块个数*/, ans/*最终答案*/;
int target;/*最终调整MST时,要寻找的节点(就是书上说的x)*/
int head[30], blc[30]/*记录每个节点属于哪个连通块*/,blcRep[30]/*每个连通块的代表节点*/;
int path[30][30];/*用邻接矩阵存图,用这种方式得到某些信息比邻接表方便*/
bool found;/*找到target节点*/
map<pair<int, int>, int> pathID;/*建立邻接矩阵中每条边与邻接表中每条边的映射,见第101行*/
vector<int> blcNod[30]/*记录每个连通块由哪些节点组成*/, fnlMST;/*fnl = final,最终的MST由哪些边组成*/

struct Edge {
    int to, nxt, wgt;
} edge[500];

struct Node {
    int pos, dis, edg/*连向这个节点的是哪条边*/;
    Node(int _pos = 0, int _dis = 0, int _edg = 0) {
        pos = _pos, dis = _dis, edg = _edg;
    }
    friend bool operator <(const Node &a, const Node &b) {
        return a.dis > b.dis;
    }
};

void addedge(int from, int to, int wgt)
{
    edge[e].to = to; 
    edge[e].wgt = wgt;
    edge[e].nxt = head[from];
    head[from] = e++; /*为了能够方便地找到一条边的反向边,使用这种方法*/
}

void dfs(int u, int f)
{
    blc[u] = cnt;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == f || v == root || blc[v]) continue;
        dfs(v, u);
    }
}

void divide()
{
    for (int i = head[root]; ~i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (blc[v] == 0) {
            cnt++;
            dfs(v, root);
            blcRep[cnt] = v;
        }
    }
}

void getMST()
{
    priority_queue<Node> pq;
    bool vis[30];
    for (int i = 1; i <= cnt; ++i) {
        memset(vis, false, sizeof vis);
        pq.push(Node(blcRep[i], 0, -1));
        while (!pq.empty()) {
            Node cur = pq.top();
            pq.pop();
            int u = cur.pos;
            if (vis[u] == true) continue;
            blcNod[i].push_back(u);
            if (~cur.edg) fnlMST.push_back(cur.edg); /*连通块内的MST一定会存在于最终的MST中*/
            if (~cur.edg) fnlMST.push_back(cur.edg ^ 1); /*反向边也要加进去*/
            ans += cur.dis; /*累加答案*/
            vis[u] = true;
            for (int j = head[u]; ~j; j = edge[j].nxt) {
                int v = edge[j].to;
                int w = edge[j].wgt;
                if (vis[v] || blc[v] != i) continue; /*不是当前连通块的节点不要考虑*/
                pq.push(Node(v, w, j));
            }
        }
    }
}

void connect()
{
    for (int i = 1; i <= cnt; ++i) {
        int minBrc/*当前连通块与根节点的所有边中权值最小值, brc = branch*/ = 0x3f3f3f3f;
//      int minSbr/*这条最小权值的边是这个连通块中哪个节点连出去的, sbr = subroot*/ = 0;
        int minEdg/*这条边到底是哪条边*/ = 0;
        for (vector<int>::iterator it = blcNod[i].begin(); it != blcNod[i].end(); ++it) {
            int u = *it;
            if (minBrc > path[u][root]) { /*如果要寻找特定的一条边的话,邻接矩阵比邻接表方便多了*/
                minBrc = path[u][root];
//              minSbr = u;
                minEdg = pathID[make_pair(u, root)]; /*我们需要知道这条边的编号*/
            }
        }
        ans += minBrc; /*累加答案*/
        fnlMST.push_back(minEdg);
        fnlMST.push_back(minEdg ^ 1); /*别忘了加反向边*/
    }
}

int getMax(int u, int f) /*在回溯时统计从target到根节点的路径上的最大边权*/
{
    if (u == target) {
        found = true;
        return 0;
    }
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (find(fnlMST.begin(), fnlMST.end(), i) == fnlMST.end()) continue;
        int v = edge[i].to;
        int w = edge[i].wgt;
        if (v == f) continue;
        int tmp = getMax(v, u);
        if (found == true) { /*找到target,直接回溯*/
            return max(tmp, w);
        }
    }
}

void select()
{
    vector<int> outside;/*从根节点出发的,不在MST中的边*/
    for (int i = head[root]; ~i; i = edge[i].nxt) {
        if (find(fnlMST.begin(), fnlMST.end(), i) == fnlMST.end()) {
            outside.push_back(i);
        }
    }
    for (int i = 1; i <= s - cnt; ++i) { /*可加入的边数上限*/
        int maxDel = -0x3f3f3f3f;/*MST权值可以减少的最大值*/
        vector<int>::iterator insrt;/*即将要插入MST的边。其实还应该从MST中
        删去一条边(被insrt替换了),不过由于只需要维护答案,就不用从fnlMST中真的删除了。*/
        for (vector<int>::iterator it = outside.begin(); it != outside.end(); ++it) {
            target = edge[*it].to;
            found = false;
            int tmp = getMax(root, 0) - edge[*it].wgt; /*计算差值*/
            if (tmp > maxDel) {
                maxDel = tmp;
                insrt = it;
            }
        }
        if (maxDel <= 0) { /*没必要在加边了,提前退出*/
            break;
        } else {
            ans -= maxDel; /*更新答案*/
            outside.erase(insrt);
        }
    }
}

void init()
{
    ios::sync_with_stdio(false);
    cin >> n;
    map<string, int> Hash;
    memset(head, -1, sizeof head);
    memset(path, 0x3f, sizeof path);
    for (int i = 1; i <= n; ++i) {
        string name1, name2;
        int ui, vi, wi;
        cin >> name1 >> name2 >> wi;
        ui = Hash[name1] ? Hash[name1] : Hash[name1] = ++tot;
        vi = Hash[name2] ? Hash[name2] : Hash[name2] = ++tot;
        if (name1 == "Park") root = ui;
        if (name2 == "Park") root = vi;
        addedge(ui, vi, wi);
        pathID.insert(make_pair(make_pair(ui, vi), e - 1));
        addedge(vi, ui, wi);
        pathID.insert(make_pair(make_pair(vi, ui), e - 1));
        path[ui][vi] = path[vi][ui] = min(path[ui][vi], wi);
    }
    for (int i = 1; i <= tot; ++i) {
        path[i][i] = 0;
    }
    cin >> s;
}

void work()
{
    divide(); /*分割连通块*/
    getMST(); /*求解每个连通块内的MST*/
    connect(); /*连通块向根节点连边*/
    /*
        puts("-----DEBUG INFO-----");
        for (vector<int>::iterator it = fnlMST.begin(); it != fnlMST.end(); ++it) {
            printf("edge %d, v = %d, w = %d\n", *it, edge[*it].to, edge[*it].wgt);
        }
        putchar('\n');
        puts("-----DEBUG INFO-----");
    */
    select(); /*调整最终MST*/
    printf("Total miles driven: %d", ans); /*输出最终答案*/
}

int main()
{
    init();
    work();
    return 0;
}


活动打卡代码 AcWing 383. 观光

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005, MAXM = 10005;

int t, n, m, s, f, e;
int head[MAXN], dist[MAXN][2], cnt[MAXN][2];

struct Edge {
    int to, nxt, wgt;
} edge[MAXM];

struct Node {
    int pos, dis, mod;
    Node(int _pos = 0, int _dis = 0, int _mod = 0) {
        pos = _pos, dis = _dis, mod = _mod;
    }
    friend bool operator <(const Node &a, const Node &b) {
        return a.dis > b.dis;
    }
};
priority_queue<Node> pq;

inline void addedge(int from, int to, int wgt)
{
    edge[++e].to = to;
    edge[e].wgt = wgt;
    edge[e].nxt = head[from];
    head[from] = e;
}

void init()
{
    e = 0;
    memset(head, 0, sizeof head);
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= m;++i) {
        int ui, vi, wi;
        scanf("%d%d%d", &ui, &vi, &wi);
        addedge(ui, vi, wi);
    }
    scanf("%d%d", &s, &f);
    dist[s][0] = 0;
    cnt[s][0] = 1;
}

void work()
{
    pq.push(Node(s, 0, 0));
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int u = cur.pos, k = cur.mod;
        if (dist[u][k] != cur.dis) continue;
        for (int i = head[u];i;i = edge[i].nxt) {
            int v = edge[i].to;
            int d = dist[u][k] + edge[i].wgt;
            if (dist[v][0] > d) {
                if (dist[v][0] != 0x3f3f3f3f) {
                    dist[v][1] = dist[v][0];
                    cnt[v][1] = cnt[v][0];
                    pq.push(Node(v, dist[v][1], 1));
                }
                dist[v][0] = d;
                cnt[v][0] = cnt[u][k];
                pq.push(Node(v, dist[v][0], 0));
            } else if (dist[v][0] == d) {
                cnt[v][0] += cnt[u][k];
            } else if (dist[v][1] > d) {
                dist[v][1] = d;
                cnt[v][1] = cnt[u][k];
                pq.push(Node(v, dist[v][1], 1));
            } else if (dist[v][1] == d) {
                cnt[v][1] += cnt[u][k];
            }
        }
    }
    printf("%d\n", cnt[f][0] + (dist[f][0] + 1 == dist[f][1] ? cnt[f][1] : 0));
}

int main()
{
    scanf("%d", &t);
    for (int caseID = 1;caseID <= t;++caseID) {
        init();
        work();
    }
    return 0;
}


活动打卡代码 AcWing 345. 牛站

Initialize.
9个月前
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, t, s, e, len, nid;
int path[MAXN][MAXN], res[MAXN][MAXN], edge[105][3], pos[1005], node[2005];

void multiply(int matA[MAXN][MAXN], int matB[MAXN][MAXN]) {
    int tmp[MAXN][MAXN];
    memset(tmp, 0x3f, sizeof tmp);
    for (int i = 1;i <= len;++i) {
        for (int j = 1;j <= len;++j) {
            for (int k = 1;k <= len;++k) {
                tmp[i][j] = min(tmp[i][j], matA[i][k] + matB[k][j]);
            }
        }
    }
    memcpy(matA, tmp, sizeof tmp);
}

void init()
{
    scanf("%d%d%d%d", &n, &t, &s, &e);
    for (int i = 1;i <= t;++i) {
        scanf("%d%d%d", &edge[i][2], &edge[i][0], &edge[i][1]);
        node[++nid] = edge[i][0];
        node[++nid] = edge[i][1];
    }
    sort(node + 1,  node + nid + 1);
    len = unique(node + 1, node + nid + 1) - (node + 1);
    for (int i = 1;i <= 1000;++i) {
        pos[i] = lower_bound(node + 1, node + len + 1, i) - node;
    }
    memset(path, 0x3f, sizeof path);
//  for (int i = 1;i <= len;++i) path[i][i] = 0;
    for (int i = 1;i <= t;++i) {
        path[pos[edge[i][0]]][pos[edge[i][1]]] =
        path[pos[edge[i][1]]][pos[edge[i][0]]] = edge[i][2];
//      printf("%d %d\n", pos[edge[i][0]], pos[edge[i][1]]);
    }
    /*
        for (int i = 1;i <= len;++i) {
            for (int j = 1;j <= len;++j) {
                printf("%d ", path[i][j]);
            }
            putchar('\n');
        }
    */
    n--;
}

void work()
{
    memcpy(res, path, sizeof path);
    while (n) {
        if (n & 1) multiply(res, path);
        n >>= 1;
        multiply(path, path);
    }
//  printf("%d %d", res[pos[s]][pos[e]], len);
    printf("%d", res[pos[s]][pos[e]]);
}

int main()
{
    init();
    work();
    return 0;
}