头像

胖鸽

芜湖市第二十七中学




离线:5天前


新鲜事 原文

胖鸽
11天前
祝大家今年大吉大利,考试顺利,hh
图片



胖鸽
13天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if (i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ )  dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == 0x3f3f3f3f)  puts("impossible");
    else cout << t << endl;

    return 0;
}



胖鸽
13天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int res, cnt;
int fa[N];

struct Edge
{
    int a, b, w;
    bool operator< (const Edge &e) const
    {
        return w < e.w;
    }
} edges[N * 2];

int find(int x)
{
    if (fa[x] == x) return fa[x];
    fa[x] = find(fa[x]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) fa[i] = i;

    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)
        {
            fa[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt >= n - 1) cout << res << endl;
    else cout << "impossible" << endl;

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

胖鸽
13天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;

int n, m, k;
int f[N][N];

void floyed()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    return;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; i ++ )  f[i][i] = 0;

    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = min(f[a][b], c);
    }

    floyed();

    for (int i = 1; i <= k; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if (f[x][y] >= 0x3f3f3f3f / 2) puts("impossible");
        else printf("%d\n", f[x][y]);
    }

    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

胖鸽
13天前
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 150010, M = N * 2;
typedef pair<int, int> PII;

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

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

int spfa()
{
    dist[1] = 0;
    queue<int> q;

    for (int i = 1; i <= n; i ++)
    {
        st[i] = 0;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                    q.push(j), st[j] = true;
            }
        }
    }

    return false;
}

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

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

胖鸽
14天前
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
int h[N], w[N];

bool check(int mid)
{
    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += (LL)h[i] / mid * (w[i] / mid);
        if (res >= m)   return true;
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )   cin >> h[i] >> w[i];
    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;return 0;
}


活动打卡代码 AcWing 445. 数字反转

胖鸽
14天前
#include <iostream>

using namespace std;

int main()
{
    int x, f = 1;
    cin >> x;

    if (x < 0)
        f = -1, x = -x;

    int gg = 0;
    while (x)
    {
        gg = gg * 10 + x % 10;
        x /= 10;
    }
    cout << gg * f << endl;
    return 0;
}


活动打卡代码 AcWing 89. a^b

胖鸽
14天前
#include <iostream>

using namespace std;

long long a, b, p;

long long work()
{
    long long res = 1 % p;
    while (b)
    {
        if (b & 1)  res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }

    return res;
}

int main()
{
    cin >> a >> b >> p;
    cout << work() << endl;
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

胖鸽
14天前
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 150010, M = N * 2;
typedef pair<int, int> PII;

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

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    st[1] = true;
    queue<int> q;
    q.push(1);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; 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;
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f)  return -1;
    return dist[n];
}

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

    if (spfa() == -1) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}



胖鸽
14天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
struct Edge
{
    int a, b, w;
}e[M];
int dist[N], backup[N];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int j = 1; j <= k; j ++ )
    {
        memcpy(backup, dist, sizeof dist);
        for (int i = 1; i <= m; i ++ )
        {
            int a = e[i].a, b = e[i].b, w = e[i].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[i].a = a, e[i].b = b, e[i].w = w;
    }

    if (bellman_ford() == -1) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}