头像

慕明




离线:14天前


最近来访(100)
用户头像
xyzfrozen
用户头像
是你
用户头像
黑帮大白菜
用户头像
重生之我是闫学灿yxc
用户头像
LIERLIER
用户头像
no_one
用户头像
魔法学徒
用户头像
按时睡觉
用户头像
Seveness
用户头像
yuefanxiao
用户头像
pccc
用户头像
诗人kris
用户头像
yrf_zwh
用户头像
无意秋风
用户头像
qing_lin
用户头像
77777777777
用户头像
老老老帅比
用户头像
123_34
用户头像
Dumby_cat
用户头像
ACWING__1227

活动打卡代码 AcWing 1145. 北极通讯网络

慕明
4个月前

思路:按边权排序跑kruskal最小生成树,使用并查集合并时每次扩展一个结点,当未扩展的结点数为k-1的时候,说明剩下的结点可以互相通讯并且能与当前生成树通讯,此时退出循环即可
graph.png
合并完再删是错误的,如图如果有4台卫星设备,如果是删掉最大的两条边应该是1,2,3,4配置设备,但实际上是2,3,4,5配置设备

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
const int N = 505;
int pos[N][2], p[N];
bool vis[N];
typedef long long ll;
int find(int x) {
    return x == p[x] ? x : (p[x] = find(p[x]));
}
ll getDist(int r1, int c1, int r2, int c2) {
    return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
bool cmp(vector<ll>& a, vector<ll>& b) {
    return a[2] < b[2];
}
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> pos[i][0] >> pos[i][1], p[i] = i;
    if(k >= n) {
        cout << "0.00";
        return 0;
    }
    vector<vector<ll>> e;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            e.push_back({ i, j, getDist(pos[i][0], pos[i][1], pos[j][0], pos[j][1]) });
        }
    }
    sort(e.begin(), e.end(), cmp);
    int cnt = 1;
    double ans = 0;
    for (int i = 0; i < e.size(); i++) {
        auto v = e[i];
        if (find(v[0]) != find(v[1])) {
            p[find(v[0])] = find(v[1]);
            ans = v[2];
            ++cnt;
            if(n - cnt == k - 1) {
                break;
            }
        }
    }
    ans = sqrt(ans);
    printf("%.2f", ans);
    return 0;
}


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

慕明
5个月前
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 5e4 + 5;
int h[N], e[M], edge[M], w[M], idx;
int scc[N], low[N], dfn[N], instk[N], siz[N], tot, cnt;
stack<int> stk;
void add(int u, int v) {
    e[idx] = v;
    edge[idx] = h[u];
    h[u] = idx++;
}
void tarjan(int x) {
    low[x] = dfn[x] = ++tot;
    stk.push(x), instk[x] = 1;
    for (int i = h[x]; i != -1; i = edge[i]) {
        int ne = e[i];
        if (!dfn[ne]) {
            tarjan(ne);
            low[x] = min(low[ne], low[x]);
        }
        else if (instk[ne]) {
            low[x] = min(low[x], dfn[ne]);
        }
    }
    if (dfn[x] == low[x]) {
        int y;
        ++cnt;
        do {
            y = stk.top();
            stk.pop();
            instk[y] = 0;
            scc[y] = cnt;
            siz[cnt]++;
        } while (y != x);
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v) {
            add(i, v);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    vector<int> idg(cnt + 1), odg(cnt + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; j != -1; j = edge[j]) {
            int ne = e[j];
            if (scc[i] != scc[ne]) {
                idg[scc[ne]]++, odg[scc[i]]++;
            }
        }
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= cnt; i++) {
        if (idg[i] == 0) ++ans1;
        if (odg[i] == 0) ++ans2;
    }
    // 入度为0的个数
    cout << ans1 << "\n";
    // 入度为0和出度为0的最大值,如1->3,2->3,要使他们变成强连通分量,则需要加3->1,3->2;又如1->2,1->3,要使他们变成强连通分量,则需要加2->1,3->1
    if (cnt > 1) cout << max(ans1, ans2);
    else cout << 0;
    return 0;
}


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

慕明
5个月前
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 5e4 + 5;
int h[N], e[M], edge[M], w[M], idx;
int scc[N], low[N], dfn[N], instk[N], siz[N], tot, cnt;
stack<int> stk;
void add(int u, int v) {
    e[idx] = v;
    edge[idx] = h[u];
    h[u] = idx++;
}
void tarjan(int x) {
    low[x] = dfn[x] = ++tot;
    stk.push(x), instk[x] = 1;
    for (int i = h[x]; i != -1; i = edge[i]) {
        int ne = e[i];
        if (!dfn[ne]) {
            tarjan(ne);
            low[x] = min(low[ne], low[x]);
        }
        else if (instk[ne]) {
            low[x] = min(low[x], dfn[ne]);
        }
    }
    if (dfn[x] == low[x]) {
        int y;
        ++cnt;
        do {
            y = stk.top();
            stk.pop();
            instk[y] =
            scc[y] = cnt;
            siz[cnt]++;
        } while (y != x);
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    vector<vector<int>> g(cnt + 1);
    vector<int> odg(cnt + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; j != -1; j = edge[j]) {
            int ne = e[j];
            if (scc[i] != scc[ne]) {
                g[scc[i]].push_back(scc[ne]), odg[scc[i]]++;
            }
        }
    }
    int ans = 0, zero = 0;
    for (int i = 1; i <= cnt; i++) {
        if (odg[i] == 0) ans = siz[i], ++zero;
    }
    // 如果存在多个出度为0的点,则输出0
    if (zero > 1) cout << 0;
    else cout << ans;
    return 0;
}


活动打卡代码 AcWing 340. 通信线路

慕明
7个月前

假设我们二分出一个值x,那意味着x应该满足:从 1→n 的路径中应该存在一条路,使得这条路上最多有k条大于x的边。
我们将大于x的边权设为1,小于等于x的边权设为0,如果1->n的最短路$dist[n]<=k$则不断向左二分

#include<bits/stdc++.h>
using namespace std;
const int N = 1005, M = 2e4 + 5;
int n, m, k;
int h[N], ne[M], e[M], w[M], idx, st[N], dist[N];
void add(int a, int b, int c) {
    ne[idx] = h[a];
    e[idx] = b;
    w[idx] = c;
    h[a] = idx++;
}
struct HeapNode {
    int id, val;
    bool operator < (const HeapNode& t) const {
        return val > t.val;
    }
};
bool dijkstra(int x) {
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dist[1] = 0;
    priority_queue<HeapNode> q;
    q.push({1, 0});
    while(!q.empty()) {
        auto node = q.top();
        q.pop();
        int t = node.id;
        if(st[t]) continue;
        st[t] = true;
        for(int i = h[t];i != -1;i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[t] + (w[i] > x)) {
                dist[j] = dist[t] + (w[i] > x);
                q.push({j, dist[j]});
            }
        }
    }
    return dist[n] <= k;
}
int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m >> k;
    for(int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra(0);
    if(dist[n] == 0x3f3f3f3f) {
        cout << -1;
        return 0;
    }
    int l = 0, r = 1e8;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(dijkstra(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r;
    return 0;
}


活动打卡代码 AcWing 1135. 新年好

慕明
7个月前

先预处理从$1,a,b,c,d,e$为起点到其他点的单源最短路,暴力枚举所有路径$5!$种,通过查表方式计算路径最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, M = 2e5 + 5;
int h[N], ne[M], e[M], w[M], idx;
int tar[6], dist[6][N], vis[N];
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}
struct HeapNode {
    int id, val;
    bool operator < (const HeapNode& t) const {
        return val > t.val;
    }
};
void dijkstra(int s, int id) {
    memset(dist[id], 0x3f, sizeof(dist[id]));
    memset(vis, 0, sizeof(vis));
    dist[id][s] = 0;
    priority_queue<HeapNode> q;
    q.push({s, 0});
    while(!q.empty()) {
        auto node = q.top();
        q.pop();
        int t = node.id;
        if(vis[t]) continue;
        vis[t] = true;
        for(int i = h[t];i != -1;i = ne[i]) {
            int j = e[i];
            if(dist[id][j] > dist[id][t] + w[i]) {
                dist[id][j] = dist[id][t] + w[i];
                q.push({j, dist[id][j]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    unordered_map<int, int> mp;
    tar[0] = 1;
    for(int i = 1;i <= 5;i++) cin >> tar[i], mp[tar[i]] = i;
    mp[1] = 0;
    for(int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    for(int i = 0;i <= 5;i++) dijkstra(tar[i], mp[tar[i]]);
    sort(tar + 1, tar + 6);
    int ans = 0x3f3f3f3f;
    do {
        int sum = 0;
        for(int i = 0;i < 5;i++) {
            sum += dist[mp[tar[i]]][tar[i + 1]];
        }
        ans = min(sum ,ans);
    } while(next_permutation(tar + 1, tar + 6));
    cout << ans << "\n";
    return 0;
}


活动打卡代码 AcWing 1077. 皇宫看守

慕明
7个月前

$f[i][0]$:第i个结点被父节点观察
$f[i][1]$:第i个结点被至少一个子节点观察
$f[i][2]$:第i个结点本身有哨兵
$f[i][0] = ∑min(f[j][1], f[j][2])$
$f[i][1] = 枚举k有哨兵∑(f[k][2] + f[i][0] - min(f[k][1], f[k][2]))$
$f[i][2] = ∑min(f[j][0], f[j][1], f[j][2])$

#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
int h[N], ne[N], w[N], e[N], idx, not_root[N];
int f[N][3];
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int node) {
    f[node][2] = w[node];
    for (int i = h[node]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[node][0] += min(f[j][1], f[j][2]);
        f[node][2] += min(f[j][0], min(f[j][1], f[j][2]));
    }
    f[node][1] = 1e9;
    for (int i = h[node]; i != -1; i = ne[i]) {
        int j = e[i];
        f[node][1] = min(f[node][1], f[j][2] + f[node][0] - min(f[j][1], f[j][2]));
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    int n;
    scanf("%d", &n);
    for(int i = 0;i < n;i++) {
        int id, m, wg;
        scanf("%d%d%d", &id, &wg, &m);
        w[id] = wg;
        for(int j = 0;j < m;j++) {
            int b;
            scanf("%d", &b);
            add(id, b);
            not_root[b] = 1;
        }
    }
    int root;
    for(int i = 1;i <= n;i++) {
        if(!not_root[i]) root = i;
    }
    dfs(root);
    printf("%d", min(f[root][1], f[root][2]));
    return 0;
}


活动打卡代码 AcWing 323. 战略游戏

慕明
7个月前

观察的是边而不是点,所以必有$dp[i][0] = dp[e[i]][1]$

#include<bits/stdc++.h>
using namespace std;
// 状态表示:dp[i][j]表示当前节点i状态为j,使以i为根节点的子树合法的最少士兵数,j=0表示不选,j=1表示选
const int N = 1505;
int f[N][2];
int h[N], ne[N], e[N], idx;
bool not_root[N];
void add(int a, int b) {
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}
void dfs(int node) {
    if(h[node] == -1) {
        f[node][0] = 0;
        f[node][1] = 1;
        return;
    }
    int res1 = 0, res2 = 0;
    for(int i = h[node];i != -1;i = ne[i]) {
        dfs(e[i]);
        res2 += f[e[i]][1], res1 += min(f[e[i]][0], f[e[i]][1]);
    }
    f[node][0] = res2;
    f[node][1] = res1 + 1;
}
int main()
{
    int n;
    while(scanf("%d", &n) != EOF) {
        memset(h, -1, sizeof(h));
        idx = 0;
        memset(not_root, 0, sizeof(not_root));
        memset(f, 0x3f, sizeof(f));
        for(int i = 0;i < n;i++) {
            int m, a;
            scanf("%d:(%d)", &a, &m);
            for(int j = 0;j < m;j++) {
                int b;
                scanf("%d", &b);
                add(a, b);
                not_root[b] = 1;
            }
        }
        int root;
        for(int i = 0;i < n;i++) {
            if(!not_root[i]) root = i;
        }
        dfs(root);
        cout << min(f[root][0], f[root][1]) << "\n";
    }
    return 0;
}


活动打卡代码 AcWing 1074. 二叉苹果树

慕明
7个月前

树上分组背包

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
// 状态表示:dp[i][j]表示第i个结点保留j个树枝的最大苹果数量,这j个树枝是与其连通的子树边
int dp[N][N], n, m, inf;
int h[N], ne[N], w[N], e[N], idx;
void add(int a, int b, int c) {
    ne[idx] = h[a];
    e[idx] = b;
    w[idx] = c;
    h[a] = idx++;
}
void dfs(int node, int fa) {
    dp[node][0] = 0;
    for(int i = h[node];i != -1;i = ne[i]) {
        if(e[i] == fa) continue;
        dfs(e[i], node);
        for(int k = n;k >= 0;k--) {
            for(int j = 0;j <= n;j++) {
                if(k - j - 1 >= 0) dp[node][k] = max(dp[node][k], dp[node][k - j - 1] + dp[e[i]][j] + w[i]);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(dp, -0x3f, sizeof(dp));
    memset(h, -1, sizeof(h));
    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);
    }
    dfs(1, -1);
    cout << dp[1][m] << "\n";
    return 0;
}


活动打卡代码 AcWing 1073. 树的中心

慕明
7个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], son[N];
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}
void dfs_up(int node, int fa) {
    for(int i = h[node];i != -1;i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        dfs_up(j, node);
        int res = d1[j] + w[i];
        if(res >= d1[node]) {
            d2[node] = d1[node];
            d1[node] = res;
            son[node] = j;
        }
        else if(res > d2[node]) {
            d2[node] = res;
        }
    }
}
void dfs_down(int node, int fa) {
    for(int i = h[node];i != -1;i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        if(son[node] == j) up[j] = max(up[node], d2[node]) + w[i];
        else up[j] = max(up[node], d1[node]) + w[i];
        dfs_down(j, node);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    memset(h, -1, sizeof(h));
    for(int i = 0;i < n - 1;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dfs_up(1, -1);
    dfs_down(1, -1);
    int ans = 0x3f3f3f3f;
    for(int i = 1;i <= n;i++) ans = min(ans, max(d1[i], up[i]));
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 1072. 树的最长路径

慕明
7个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
int h[N], w[N], ne[M], e[N], idx, ans;
void add(int a, int b, int c) {
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int node, int fa) {
    int dist = 0, d1 = 0, d2 = 0;
    for(int i = h[node];i != -1;i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        int res = dfs(j, node) + w[i];
        dist = max(res, dist);
        if(res >= d1) d2 = d1, d1 = res;
        else if(res > d2) d2 = res;
    }
    ans = max(d1 + d2, ans);
    return dist;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    memset(h, -1, sizeof(h));
    cin >> n;
    for(int i = 0;i < n - 1;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1, -1);
    cout << ans;
    return 0;
}