JOI本選に向けてアルゴリズムを整理しておく

まだまだアルゴリズムを覚えれていない気がするのでちょっと整理

情報落ちしていることが多数なので

参考までにお願いします

ダイクストラ法

AiとBiを距離Ciで結ぶなんか出てきたら疑っていい

//距離記録用のテーブル
ll dist[100010];

//辺
struct edge
{
    int to;
    ll cost;
};

//辺を記録
//edges[a].push_back({b,c});という感じで
vector<edge> edges[100010];

//queueに突っ込む型を用意
typedef pair<ll,int> P;

priority_queue<P,vector<P>,greater<P>> que;

//初期値
dist[1] = 0;
que.push(P(0,1));


while(!que.empty())
{
    ll d = que.top().first;
    ll v = que.top().second;
    que.pop();

    //無くても動くし、無い方がいい場合がある
    if(d > dist[v]) continue;
    
    //C++11のforeach
    for(edge& e : edges[v])
    {
        if(d[e.to] < d + e.cost)
        {
            d[e.to] = d + e.cost;
            que.push(P(d[e.to],e.to));
        }
    }
}

ベルマンフォード法

負の辺があってもできる

for(int i = 0;i < V;i++) d[i] = 1000000;

//最初の点は距離はゼロ
d[1] = 0;

while(true)
{
    bool update = false;
    for(int i = 0;i < E;i++)
    {
        const edge& e = es[i];
        if(d[e.from] != 1000000 && d[e.to] > d[e.from] + e.cost)
        {
        d[e.to] = d[e.from] + e.cost;
        update = true;
        }
    }
    if(update == false) break;
}

外側のwhileループはV - 1回しか行われないもしV回目に辺の更新が行われたなら負の閉路があることにある

経路を示すとき

ダイクストラ法であれば値を更新する際に

prev[e.to] = v;

としてやれば目的の頂点から始点までを辿れる

Union-Find木

グループ分けが必要なとき

struct UnionFind
{
    vector<int> par;
    vector<int> rank;

    UnionFind(int sz) : par(sz) , rank(sz,0)
    {
        for(int i = 0;i < sz;i++)
        {
            par[i] = i;
        }
    }

    int root(int x)
    {
        return  par[x] == x ? x : par[x] = root(par[x]);
    }
    bool unite(int x,int y)
    {
        x = root(x);
        y = root(y);
        if(x == y)
            return true;

        if(rank[x] < rank[y])
        {
            par[x] = y;
        }
        else
        {
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
        return  false;
    }

    bool same(int x,int y)
    {
        return root(x) == root(y);
    }
};

二分木探索

lower_bound...x以上の数で最小の数
upper_bound...xより大きい数で最小の数

配列はソートしておかないと使えない

ナップサックDP

これを見て気分を落ち着かせましょう

DPは幅が多すぎてア

Segment Tree

区間に対しての操作に強い

これを解いておこう

値の更新は下から

値の取得は上からというのをベースに考えておけばOK

ll MAX = (ll)(1LL<<31) - 1LL;
struct Segment
{
    vector<ll> node;
    int n;
 
    Segment(const vector<ll>& v)
    {
        int sz = v.size();
        n = 1;
        while(n < sz) n *= 2;
 
        node.resize(n * 2 - 1,MAX);
        for(int i = 0;i < sz;i++)
        {
            node[i + n - 1] = v[i];
        }
 
        for(int i = n - 2;i >= 0;i--)
        {
            node[i] = min(node[2 * i + 1],node[2 * i + 2]);
        }
    }
 
    void update(int in,ll x)
    {
        in += n - 1;
        node[in] = x;
 
        while(in > 0)
        {
            in = (in - 1) / 2;
            node[in] = min(node[in * 2 + 1] , node[in * 2 + 2]);
        }
    }
 
    ll getmin(int a,int b,int k = 0,int l = 0,int r = -1)
    {
        if(r == -1) r = n;
 
 
        if(r <= a || b <= l) return MAX;
 
 
        if(a <= l && r <= b) return node[k];
        ll nl,nr;
 
        nl = getmin(a,b,2 * k + 1,l,(l + r)/2);
        nr = getmin(a,b,2 * k + 2,(l + r)/2,r);
 
        return min(nl,nr);
    }
};

i += n - 1を頭に入れておきたい

遅延評価Segment Tree

遅延評価する...eval(int k,int l,int r)

値を区間で変化させる...getminみたいにlazy[]に入れていく、このとき

1.最初に評価する(eval)
2.値を変化させた後、評価させる

これを基本に

前に書いてた記事

トポロジカルソート

有向グラフが順方向になるようにソートする方法

vector<int> edge[10010];

//入次数
int h[10010];

int V;
int E;

    cin >> V;
    cin >> E;

    for(int i = 0;i < E;i++)
    {
        int s;
        int t;

        cin >> s >> t;

        edge[s].push_back(t);

    //向かってきている辺の数をカウントする
        h[t]++;
    }

    stack<int> st;

    for(int i = 0;i < V;i++)
    {
        if(h[i] == 0) st.push(i);
    }

    vector<int> topolo;

    while(!st.empty())
    {
        int v = st.top();
        st.pop();

        topolo.push_back(v);

        for(int to : edge[v])
        {
            h[to]--;

            if(h[to] == 0)
            {
                st.push(to);
            }
        }
    }

入次数が0のところをstackに突っ込んでいく感じ

またこれをqueueにすると違う経路が得られる可能性がある

思いつく限りで書きました

もっとあると思うがここには余白が狭すぎるし

何しろ自分の知識の幅が狭すぎる