头像

a_pig_of_banana




离线:13小时前


最近来访(7)
用户头像
种花家的市长
用户头像
早点睡觉_1
用户头像
有机物
用户头像
故人倾
用户头像
LI冬天
用户头像
At_sunrise


题目链接 SPFA判断负环

我不知道为什么不要初始化。却通过了。

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;
    }
}

这个if不加初始化应该会出错吧??




#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1500010;
int h[N], e[N], w[N], ne[N], idx;
int n, m;

bool b[N];
int dist[N];

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

int dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    heap.push({0, 1});

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

        int distance = t.first, ver = t.second;

        if(b[ver]) continue;
        b[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(distance + w[i] < dist[j])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

int main()
{
    ios :: sync_with_stdio(false), cin.tie(0);
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while(m --)
    {
        int a, b, c;

        cin >> a >> b >> c;
        add(a, b, c);
    }

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

    return 0;
}



dijkstra 算法 O(N ^ 2)

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0)
#define T true
#define F false

using namespace std;

typedef int I;
typedef bool B;

const I N = 510;

I g[N][N];
I n, m;

B b[N];
I dist[N];

I dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(I i = 0; i < n - 1; i ++)
    {
        I t = -1;

        for(I j = 1; j <= n; j ++)
            if(!b[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for(I j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        b[t] = T;
    }

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

int main()
{
    cin_Quick;
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while(m --)
    {
        I a, b, w;

        cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w);
    }

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

    return 0;
}




题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

样例

输入
3 3
1 2 2
2 3 1
1 3 4
输出
3

数据范围

1 ≤ n ≤ 500,
1 ≤ m ≤ 1e5,
图中涉及边长均不超过10000。


数据范围说明这是稠密图, 无负权边, 算法 —> dijkstra 算法

朴素 dijkstra 算法时间复杂度:

$O(N ^ 2)$


C++ 代码

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0) 
#define T true
#define F false 

using namespace std;

typedef int I;
typedef bool B;

// ---------- 以上是减代码的 TYPEDEF 和 DEFINE (虽然有一点多余)----------

const I N = 510;

I g[N][N];
I n, m;

B b[N];  // 已确定最短路的点
I dist[N];

// 最短路开始!!

I dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;                           // 初始化 dist 数组

    for(I i = 0; i < n - 1; i ++)
    {
        I t = -1;

        for(I j = 1; j <= n; j ++)
            if(!b[j] && (t == -1 || dist[t] > dist[j]))  // 找出现在不在 b 数组中的, 距离最近的点
                t = j;

        for(I j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]); // 用 t 去更新其他的点

        b[t] = T;  // t 已确定
    }

    if(dist[n] == 0x3f3f3f3f) return -1;  // 和初始数相同, 说明 1 到 n 无最短路
    return dist[n];                       // 否则返回最短路长度
}

int main()
{
    cin_Quick;  // cin 加速
    memset(g, 0x3f, sizeof g); // 初始化 g 数组

    cin >> n >> m; 
    while(m --)
    {
        I a, b, w;

        cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w);  // 由于重边的原因,只需要保留最短的一条边
    } // 输入

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

    return 0;
}// over

制作不易, 麻烦给颗小星星( ̄ω ̄)




题目描述

给定一个 n个点 m 条边的有向图,点的编号是 1 到 n ,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y) ,x 在 A 中都出现在 y 之前,则称 A是该图的一个拓扑序列。

样例

输入
3 3
1 2
2 3
1 3
输出
1 2 3

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef queue<int> ns;
typedef int I;

const I N = 100010;
I h[N], e[N], ne[N];
I idx;

I d[N];

I n, m;
ns ans;

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

bool topsort()
{
    ns q;
    I tt = -1;

    for(I i = 1; i <= n; i ++)
        if(!d[i])
            q.push(i), tt ++;

    while(q.size())
    {
        I t = q.front();
        ans.push(t);
        q.pop();

        for(I i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            d[j] --;
            if(!d[j]) q.push(j), tt ++;
        }
    }

    return tt == n - 1;
}

I main()
{
    ios::sync_with_stdio(false),cin.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while(m --)
    {
        I a, b;

        cin >> a >> b;
        add(a, b);

        d[b] ++;
    }

    if(topsort())
    {
        for(I i = 0; i < n; i ++) printf("%d ", ans.front()), ans.pop();
    }
    else puts("-1");

    return 0;
}

看不懂别见怪
若不是error了, typedef 和 define 可能还会跟多, 见谅 ~( ̄. ̄)~ hh



新鲜事 原文

AcWing【集日历瓜分10000AC币活动】求10月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/208226/10/



核对了好几遍 找不出答案

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;
int p[N], d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }

    return p[x];
}

int main()
{
    int n, k, res = 0;

    cin >> n >> k;

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

    while(k --)
    {
        int D;
        int x, y;

        cin >> D >> x >> y;

        if(x > n || y > n) res ++;
        else
        {
            int px = find(x), py = find(y);

            if(D == 1)
            {
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else 
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else 
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    cout << res << endl;
    return 0;
}

求助!!



新鲜事 原文

加了ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0); cin,cout比scanf,printf快


题目讨论 AcWing 828. what!!!!!!

我这有什么问题吗??!! 有个测试点明明输出和答案一样, 它还WA!!!

#include <iostream>

using namespace std;

const int N =  100010;
int QuickStack[N];

int head;

void push(int x){ QuickStack[++ head] = x; }

void pop(){ head --; }

bool empty(){ return head == 0; }

int query(){ return QuickStack[head]; }

int main()
{
    ios :: sync_with_stdio(false),
    cin.tie(0), 
    cout.tie(0);

    int n;

    cin >> n;
    while(n --){
        string que;
        int x;

        cin >> que;

        if(que == "push") cin >> x, push(x);
        else if(que == "pop") pop();
        else if(que == "query") cout << query() << endl;
        else cout << (empty() ? "Yes" : "No") << endl;
    }

    return 0;
}


新鲜事 原文

``` #include <iostream> #include <vector> #define quik ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; vector<int> add(vector<int> &A, vector<int> &B){ if(A.size() < B.size()) return add(B, A); vector<int> ans; int t = 0; for(int i = 0; i < A.size(); i ++){ t += A[i]; if(B.size() > i) t += B[i]; ans.push_back(t % 10); t /= 10; } if(t) ans.push_back(t); return ans; } int main(){ quik; string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0'); auto ans = add(A, B); for(int i = ans.size() - 1; i >= 0; i --) cout << ans[i]; cout << endl; return 0; } ```