头像

LHHHHHH

$\color{red}{\textsf{yxc追随者}}$




离线:19小时前


最近来访(49)
用户头像
归期
用户头像
hair++
用户头像
apwc
用户头像
Zrosor_Acw
用户头像
taoist
用户头像
tibiks
用户头像
食物链生存法则
用户头像
Hygen
用户头像
bxiao0801
用户头像
ghy
用户头像
云山如昨好
用户头像
心向远方
用户头像
Bino
用户头像
用java的程序员
用户头像
gaumn
用户头像
ArkhamKnight
用户头像
lovepeace
用户头像
名字好怪
用户头像
雾岛少帅
用户头像
有一个地方

活动打卡代码 AcWing 2171. EK求最大流

LHHHHHH
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];

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

bool bfs()
{
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (!st[ver] && f[i])
            {
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int EK()
{
    int r = 0;
    while (bfs())
    {
        r += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
    }
    return r;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", EK());

    return 0;
}


活动打卡代码 AcWing 3403. 我想回家

LHHHHHH
17天前

模板题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, pair<int, int>> PII;

const int N = 1000, M = 1e5;

int h[N], e[M], w[M], ne[M], idx;
int dist[N][2];
int type[N];
bool st[N][2];
int n, m;

void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra()  // 求1号点到n号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1][0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, {1, 0}});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y.x, tt = t.y.y;

        if (st[ver][tt]) continue;
        st[ver][tt] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(type[j] != type[ver]){
                if(tt) continue;
                else{
                    if(dist[j][1] > dist[ver][0] + w[i]){
                        dist[j][1] = dist[ver][0] + w[i];
                        heap.push({dist[j][1], {j, 1}});
                    }
                }
            }
            else{
                if(dist[j][tt] > dist[ver][tt] + w[i]){
                    dist[j][tt] = dist[ver][tt] + w[i];
                    heap.push({dist[j][tt], {j, tt}});
                }
            }
        }
    }
}


int main()
{
    while(scanf("%d", &n), n)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        scanf("%d", &m);
        while (m -- ){
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }

        for(int i = 1; i <= n; i ++ ){
            scanf("%d", &type[i]);
        }
        dijkstra();
        if(dist[2][1] == 0x3f3f3f3f) puts("-1");
        else printf("%d\n", dist[2][1]);
    }
    return 0;
}


活动打卡代码 AcWing 3556. 最短路径

LHHHHHH
17天前

参考铅笔大佬

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, INF = 0x3f3f3f3f;
int T, n, m, k;
int f[N][N];

struct E
{
    int a, b, c;
}e[N * N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i == j) f[i][j] = 0;
                else f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
        f[a][b] = f[b][a] = c;
    }
    floyd(); cout << f[1][n] << endl;
    memset(f, 0x3f, sizeof f);
    for (int i = 0, id; i < k; i ++ ) cin >> id, e[id] = {0, 0, 0};
    for (int i = 1; i <= m; i ++ )
        if (e[i].c)
            f[e[i].a][e[i].b] = f[e[i].b][e[i].a] = e[i].c;
    floyd(); cout << (f[1][n] == INF ? -1 : f[1][n]) << endl;
}
int main()
{
    cin >> T;
    while (T -- )
    {
        memset(f, 0x3f, sizeof f);
        solve();
    }
    return 0;
}


活动打卡代码 AcWing 3488. 最短路径

LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110, MOD = 1e5, INF = 0x3f3f3f3f;

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

int find(int u)
{
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}
void dfs(int u)
{
    for (int i = 0; i < n; i ++ )
    {
        if (g[u][i] == INF) continue;
        if (~f[i]) continue;
        f[i] = (f[u] + g[u][i]) % MOD;
        dfs(i);
    }
}
int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) p[i] = i;
    for (int i = 0, d = 1; i < m; i ++ , d = d * 2 % MOD)
    {
        int a, b; cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            g[a][b] = g[b][a] = d;
            p[pa] = pb;
        }
    }

    memset(f, -1, sizeof f);
    f[0] = 0;
    dfs(0);
    for (int i = 1; i < n; i ++ ) cout << f[i] << endl;
    return 0;
}



LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int a[N], n;
int f[N][N];

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

    int res = 1;

    f[1][1] = f[1][0] = 1;
    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 0 ; j <= 1 ; j ++ )
        {
            for(int k = 1 ; k < i ; k ++ )
            {
                if(a[k] > a[i] && !j)
                    f[i][j] = max(f[k][!j] + 1, f[i][j]);
                if(a[k] < a[i] && j) 
                    f[i][j] = max(f[k][!j] + 1 , f[i][j]);
            }
            res = max(f[i][j], res);
        }
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 3393. 最大序列和

LHHHHHH
17天前
#include <cstring>
#include <iostream>
#include <algorithm>

const int INF = 0x3f3f3f3f;

using namespace std;

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

    long long sum = 0, Max = -INF, x;

    for(int i = 0 ; i < n ; i++)
    {
        cin >> x;
        sum = max(sum + x, x);
        Max = max(Max, sum);
    }
    cout << Max << endl;
    return 0;
}



活动打卡代码 AcWing 3447. 子串计算

LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    string s;
    while(cin >> s)
    {
        map<string, int> hash;

        for(int i = 0 ; i < s.size() ; i ++ )
            for(int j = 1 ; j < s.size() - i + 1; j ++ )
                hash[s.substr(i, j)] ++;

        for(auto i : hash)
        {
            if(i.second > 1)
                cout << i.first << ' ' << i.second << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 3509. 棋盘遍历问题

LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n, m;
    while(cin >> n >> m)
    {
        if(n == 1 && m == 1) puts("Y");
        else if(n == 1 || m == 1) puts("N");
        else if(n % 2 == 0 || m % 2 == 0) puts("Y");
        else puts("N");
    }
    return 0;
}


活动打卡代码 AcWing 3570. 弹地小球

LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n -- )
    {
        double h, k;
        cin >> h >> k;

        double sum = h;
        for(int i = 1 ; i < k ; i ++ )
        {
            sum += h;
            h /= 2;
        }
        printf("%.2lf\n", sum);
    }
    return 0;
}


活动打卡代码 AcWing 3558. 整数和

LHHHHHH
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        int n;
        cin >> n;
        int sum = 0;
        if(n > 0)
        {
            for(int i = n ; i <= 2 * n ; i ++ ) sum += i;
        }
        else if(n < 0)
        {
            for(int i = 2 * n ; i <= n ; i ++) sum += i;
        }

        cout << sum << endl;
    }
    return 0;
}