终于开始打板子了

乘法逆元(或$exgcd$)

#include <cstdio>
// ix % p = 1 -> ix + py = 1
int exgcd(int a, int b, int& x, int& y) // ax + by = 1
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int re = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return re;
}
void solve(int i, int p)
{
    int x, y, re = exgcd(i, p, x, y);
    y = p / re;
    while (x < 0)
        x += y;
    printf("%d\n", x);
}
int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++)
        solve(i, p);
    return 0;
}

负环(或$dfs-SPFA$)

注意回溯的时候将当前节点的vis置为false

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
using namespace std;
struct edg
{
    int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN];
bool ok, vis[MAXN];
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void solve(int dq)
{
    if (vis[dq])
    {
        ok = true;
        return ;
    }
    vis[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
        if (dis[b[i].to] > dis[dq] + b[i].cost)
        {
            dis[b[i].to] = dis[dq] + b[i].cost;
            solve(b[i].to);
            if (ok)
                return ;
        }
    vis[dq] = false;
}
int main()
{
    int tim;
    scanf("%d", &tim);
    while (tim--)
    {
        memset(dis, 0, sizeof(dis));
        memset(vis, false, sizeof(vis));
        memset(g, 0, sizeof(g));
        ok = false;
        cntb = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i<= m; i++)
        {
            int srw, srx, sry;
            scanf("%d%d%d", &srx, &sry, &srw);
            adn(srx, sry, srw);
            if (srw > 0)
                adn(sry, srx, srw);
        }
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
                solve(i);
            if (ok)
            {
                puts("YE5");
                break;
            }
        }
        if (!ok)
            puts("N0");
    }
    return 0;
}

最大权路径(或tarjan缩点)

注意这里是一条路径…如果没有有向边是不能回来的…gg…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define MAXN (1000000 + 5)
#define MAXM (5000000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXM << 1];
int g[MAXN], cntb, dfn[MAXN], low[MAXN], cntdfn, belong[MAXN], a[MAXN], f[MAXN];
stack<int> s;
bool ins[MAXN];
int find(int x)
{ return (x == belong[x] ? x : (belong[x] = find(belong[x]))); }
void uni(int x, int y)
{ belong[find(x)] = find(y); }
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void tarjan(int dq)
{
    dfn[dq] = low[dq] = ++cntdfn;
    ins[dq] = true;
    s.push(dq);
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (!dfn[b[i].to])
            tarjan(b[i].to), low[dq] = min(low[dq], low[b[i].to]);
        else if (ins[b[i].to])
            low[dq] = min(low[dq], dfn[b[i].to]);
    }
    if (low[dq] == dfn[dq])
    {
        while (s.top() != dq)
        {
            ins[s.top()] = false; //
//            belong[s.top()] = dq;
            uni(s.top(), dq);
            s.pop();
        }
//        belong[dq] = dq;
        s.pop();
        ins[dq] = false;
    }
}
int solve(int dq)
{
    if (f[dq] > -INF)
        return f[dq];
    f[dq] = 0;
    for (int i = g[dq]; i; i = b[i].next)
        if (find(b[i].from) != find(b[i].to)) // != 
            f[dq] = max(f[dq], solve(find(b[i].to))); //belong[b[i].to]
    return (f[dq] = f[dq] + a[dq]);
}
int main()
{
    freopen("in.in", "r", stdin);
    memset(ins, false, sizeof(ins));
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        belong[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        if (i != find(i))
            a[find(i)] += a[i];
    for (int i = 1; i <= n; i++)
        for (int j = g[i]; j; j = b[j].next)
            if (find(b[j].from) != find(b[j].to)) // i -> j
                adn(find(b[j].from), find(b[j].to)); // i -> j
    memset(f, 0x8f, sizeof(f));
    int ans = -INF;
    for (int i = 1; i <= n; i++)
        if (f[find(i)] <= - INF)
            ans = max(ans, solve(find(i)));
    printf("%d", ans);
    return 0;
}

By 吃枣药丸的 Cansult