头像

青柠

铁道游鸡队




离线:4小时前



青柠
8天前

如果你用的是堆优化的dijkstra,并且没有过掉这个题请看这个题解

一般的对优化的迪杰斯特拉我们都是从堆中取最小值,而这个我们需要每次从堆中取最大值来更新其他点,因为我们最后找的是汇率最大的,才能保证我们答案最小



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

青柠
19天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int h[N],e[N],w[N],ne[N],idx;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int n,m;
int depth[N];
int f[N][30];

void dfs(int u,int fa){

    depth[u] = depth[fa] + 1;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j != fa){
            f[j][0] = u;
            for(int k = 1;k < 20;k ++){
                int t = f[j][k - 1];
                f[j][k] = f[t][k - 1];
            }
            dfs(j,u);
        }
    }
}

int lca(int x,int y)
{
    if(depth[x] < depth[y]) swap(x,y);

    for(int i = 19;i >= 0;i --){
        if(depth[f[x][i]] >= depth[y]){
            x = f[x][i];
        }
    }
    if(x == y) return x;
    for(int i = 19;i >= 0;i --){
        if(f[x][i] != f[y][i]){
            x = f[x][i],y = f[y][i];
        }
    }
    return f[x][0];
}

int dist[N];

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


int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    for(int i = 0;i < n - 1;i ++){
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0);

    for(int i = 0;i < m;i ++){
        int a,b;
        cin >> a >> b;
        w[a] ++;
        w[b] ++;
        int t = lca(a,b);
        w[t] -= 2;
    }

    dfs2(1,0);
    long long sum = 0;
    long long cnt = 0;
    for(int i = 2;i <= n;i ++){
        if(dist[i] == 1){
            sum ++;
        }else if(dist[i] == 0){
            cnt ++;
        }
    }

    sum += cnt * m;

    cout << sum << endl;

    return 0;
}


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

青柠
20天前
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1010;
vector<pair<int,int>>v[N]; // 建立邻接表
int n,m,k;
bool st[N];
int dist[N];
// dijkstra
bool check(int cost)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    deque<int>q;
    dist[1] = 0;
    q.push_back(1);
    while(q.size())
    {
        int t = q.front();
        q.pop_front();
        if(st[t]) continue;
        st[t] = true;
        for(auto &x : v[t]){
            if(x.second > cost){
                if(dist[x.first] > dist[t] + 1){
                    dist[x.first] = dist[t] + 1;
                    q.push_back(x.first);
                }
            }else{
                if(dist[x.first] > dist[t]){
                    dist[x.first] = dist[t];
                    q.push_front(x.first);
                }
            }
        }
    }
    return dist[n] <= k;
}

int main()
{
    // 输入n,m,k
    scanf("%d%d%d",&n,&m,&k);
    int l = 0,r = 0;
    // 左边界l,右边界r
    for(int i = 0;i < m;i ++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
        v[b].push_back({a,c});
        r = max(r,c);
    }
    int kkk = r + 1;
    r ++;
    // 二分
    while(l < r)
    {
        int mid = l + r>> 1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid + 1;
        }
    }

    if(r == kkk){
        printf("%d\n",-1);
    }
    else
    printf("%d\n",r);

    return 0;
}



活动打卡代码 AcWing 474. 龙虎斗

青柠
1个月前
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n;
LL a[N];
LL m,p1,s1,s2,p2;

int main()
{
    cin >> n;
    for(LL i = 1;i <= n;i ++)
        cin >> a[i];

    cin >> m >> p1 >> s1 >> s2;

    LL ml = 0,mr = 0;
    a[p1] += s1;
    for(LL i = 1;i < m;i ++){
        ml += a[i] * (m - i);
    }

    for(LL i = m + 1;i <= n;i ++){
        mr += a[i] * (i - m);
    }

    LL id = 0;
    LL ans = 1e9 + 10;
    if(ml > mr){
        for(LL i = m;i <= n;i ++)
        {
            if(fabs((s2 * (i - m) + mr - ml)) < ans){
                id = i;
                ans = fabs((s2 * (i - m) + mr - ml));
            }
        }
        cout << id << endl;
    }
    else{

        for(LL i = 1;i <= m;i ++)
        {
            if(fabs((s2 * (m - i) + ml - mr)) < ans){
                id = i;
                ans = fabs((s2 * (m - i) + ml - mr));
            }
        }
        cout << id << endl;

    }

    return 0;
}


活动打卡代码 AcWing 2066. 解码

青柠
1个月前
#include <iostream>
using namespace std;

int main()
{
    string str;
    cin >> str;
    string ans;

    for(int i = 0;i < str.size();i ++)
    {
        char ne = str[i + 1];
        if(ne >= '0' && ne <= '9'){
            int t = ne - '0';
            while(t --){
                ans += str[i];
            }
            i ++;
        }else{
            ans += str[i];
        }

    }

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 2065. 整除序列

青柠
1个月前
#include <iostream>
#include <cstdio>
using namespace std;

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

    do{
        printf("%lld",n);
        n = n / 2;
        if(n){
            printf(" ");
        }
    }while(n);

    return 0;
}


活动打卡代码 AcWing 717. 简单斐波那契

青柠
1个月前
#include <iostream>

using namespace std;

const int N = 50;

int f[N];

int main()
{
    int n;
    cin >> n;
    f[1] = 0;
    f[2] = 1;
    for (int i = 3 ; i <= 50 ; i ++ )
    {
        f[i] = f[i-1] + f[i-2];
    }
    for (int i = 1 ; i <= n ; i ++ )
    {
        cout << f[i] << " ";
    }
    cout << endl;
    return 0;
}



青柠
1个月前
#include <iostream>

using namespace std;

const int N = 10;

int n;
int ans[N];
bool vis[N];

void dfs(int line)
{
    if(line == n+1) 
    {
        for (int i = 1 ; i <= n ; i ++ ) cout << ans[i] << " ";
        cout << endl;
        return ;
    }

    for (int i = 1 ; i <= n ; i ++ )
    {
        if(vis[i] == false)
        {
            ans[line] = i;
            vis[i] = true;
            dfs(line+1);
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(1);
}



青柠
1个月前
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 0 ; i < 1 << n ; i ++ )
    {
        for (int j = 0 ; j < n ; j ++ )
        {
            if (i >> j & 1) cout << j + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

青柠
1个月前
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
vector<int>v1[N];
vector<int>v2[N];
int w[N];
int n,m;
int dist1[N];
int dist2[N];
bool st[N];

void spfa(int op)
{
    queue<int>q;
    if(op == 1){
        memset(dist1,0x3f,sizeof dist1);
        dist1[1] = w[1];
        q.push(1);
    }else{
        memset(dist2,-0x3f,sizeof dist2);
        dist2[n] = w[n];
        q.push(n);
    }

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        if(op == 1){
            for(auto &x : v1[t])
            {
                if(dist1[x] > min(dist1[t],w[x])){
                    dist1[x] = min(dist1[t],w[x]);
                    if(!st[x]){
                        q.push(x);
                        st[x] = true;
                    }
                }
            }
        }
        else
        {
            for(auto &x : v2[t])
            {
                if(dist2[x] < max(dist2[t],w[x])){
                    dist2[x] = max(dist2[t],w[x]);
                    if(!st[x]){
                        q.push(x);
                        st[x] = true;
                    }
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++)
    {
        cin >> w[i];
    }

    for(int i = 0;i < m;i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        if(c == 1){
            v1[a].push_back(b);
            v2[b].push_back(a);
        }
        else{
            v1[a].push_back(b);
            v1[b].push_back(a);

            v2[a].push_back(b);
            v2[b].push_back(a);
        }
    }


    spfa(1);
    spfa(2);
    int res = 0;
    for(int i = 1;i <= n;i ++)
    {
        res = max(res,dist2[i] - dist1[i]);
    }

    cout << res << endl;

    return 0;
}