Floyd

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iterator>
#include<numeric>
using namespace std;
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
//#define x first
//#define y second
#define db double
#define debug(x) cerr<<#x<<x<<endl;

const int N = 210;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n,m,Q;
int d[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 ++)
            {
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);

    for(int i = 1;i <= n; i ++)
        for(int j = 1;j <= n; j ++)
        {
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    while(m --)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);

        d[a][b] = min(d[a][b],w);
    }
    floyd();
    while(Q --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n",d[a][b]);
    }
    system("pause");
    return 0;
}

并查集

using namespace std;

const int N = 50010;

int p[N],d[N];
int n,m;
void init(int n)
{
for(int i = 1; i <= n; i ++) p[i] = i;
}

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()
{
cin >> n >> m;

init(n);

int res = 0;

while(m --)
{
    int t,x,y;
    scanf("%d%d%d",&t,&x,&y);

    if(x > n || y > n) res ++;
    else 
    {
        int px = find(x),py = find(y);
        if(t == 1)
        {
            if(px == py && (d[x] - d[y]) % 3) res ++;
            else if(px != py)
            {
                p[px] = py;
                d[px] = d[y] - d[x];
            }
        }
        else
        {
            if(px == py && (d[x] - d[y] - 1) % 3) res++;
            else if(px != py)
            {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
            }
        }
    }
}
cout<<res<<endl;


system("pause");
return 0;

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const int N = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
double a[N][N];
int gauss()
{
    int c,r;//c列r行
    for(c = 0,r = 0; c < n; c ++)
    {
        int t = r;
        for(int i = r; i < n; i ++)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;//1.找到绝对值最大的那一行
        if(fabs(a[t][c])< eps) continue;

        for(int i = c; i <= n; i ++) swap(a[t][i],a[r][i]);//2.将该行换到最上边（未固定的）
        for(int i = n; i >= c; i --) a[r][i] /= a[r][c];//3.将该行第一个数变成1,倒着

        for(int i = r + 1; i < n; i ++)
            if(fabs(a[i][c]) > eps)
                for(int j = n; j >= c;j --)
                    a[i][j] -= a[r][j] * a[i][c];
        r ++;
    }
        if(r < n)
        {
            for(int i = r; i < n; i ++)
                if(fabs(a[i][n]) > eps)
                return 2;
            return 1;
        }
        for(int i = n - 1; i >= 0; i --)
        {
            for(int j = i + 1;j < n; j ++)
            {
                a[i][n] -= a[i][j] * a[j][n];//里边会有许多为0的东东就当没看见，把第一行归零
            }
        }//处理最后得出的答案
        return 0;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n + 1; j ++)
        {
            cin >> a[i][j];
        }
    }
    int t = gauss();
    if (t == 2) puts("No solution");
    else if (t == 1) puts("Infinite group solutions");
    else
    {
        for (int i = 0; i < n; i ++ )
        {
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }

    return 0;
}

Kruskal

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int p[N];
struct edge
{
    int a,b,w;
    bool operator<(const edge & W)const{
        return w < W.w;
    }
}edges[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    else return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i ++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i] = {a,b,w};
    }
    sort(edges,edges + m);
    int res = 0,cnt = 0;//res存的是最小生成树的总长，cnt的多少条边
    for(int i = 1; i <= n; i ++) p[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)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if(cnt < n - 1) puts("impossible");
    else 
    {
        printf("%d\n",res);
    }
    system("pause");
    return 0;
}

匈牙利

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const int M = 1e5 + 10,N = 510;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a],h[a] = idx ++;
}
bool find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d%d",&n1,&n2,&m);

    memset(h, -1, sizeof h);
    while(m --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res = 0;
    for(int i = 1; i <= n1; i ++)
    {
        memset(st,false, sizeof st);//保证每个妹子都没有被男孩子考虑过
        if(find(i))res ++;
    }
    printf("%d\n",res);


    system("pause");
    return 0;
}

差分矩阵

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1010 + 10;
int q[N][N];
int sum[N][N];
int x,y,x2,y2,c,t;
void insert(int x,int y,int x2,int y2,int c)
{
    sum[x][y] += c;
    sum[x2 + 1][y] -= c;
    sum[x][y2 + 1] -= c;
    sum[x2 + 1] [y2 + 1] += c;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d",&q[i][j]);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            insert(i,j,i,j,q[i][j]);
    while(t --)
    {
        scanf("%d%d%d%d%d",&x,&y,&x2,&y2,&c);
        insert(x,y,x2,y2,c);
    }
    for(int i = 1;i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++ ) printf("%d ",sum[i][j]);
        printf("\n");
    }

    system("pause");
    return 0;

TRIE字符串

//https://www.acwing.com/video/260/
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 20010;
int son[N][26],cnt[N],idx;//下标是0的点，既是根结点，又是空结点
char str[N];
void insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}
int query(char  str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u])return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(*op == 'I') insert(str);
        else cout<<query(str)<<endl;
    }




    system("pause");
    return 0;
}
//高效地存储和查找字符串

高精度除法

#include <bits/stdc++.h>
using namespace std;
// A/b,商是C，余数是r
inr r;
vector<int> mul(vector<int> &A,int b,int &rand)
{
    vector<int>C;
    r = 0;
    for(int i = A.size() - 1; i >= 0; i --)
    {
        r =r * 10 + A[i];
        C.push_back(r/b);
        r %= 10;
    }
    reverse(C.begin(),C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >>a >> b;
    if(b == 0) 
    {
        printf("0");
        return 0;
    }
    vector<int>A;
    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    auto C = div(A,b,r);
    for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);
    cout<<endl;
    cout<<r<<endl;
    system("pause");
    return 0;

染色法判断二分图

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define x first
#define y second

const int N = 1e5 + 10,M = 2 * N;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool dfs(int u,int c)
{
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c)) return false;
        }
         else if(color[j] == c) return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    bool flag = true;
    for(int i = 1; i <= n; i ++)
            if(!color[i])
            {
                if(!dfs(i,1))
                {
                    flag = false;
                    break;
                }
            }
    if(flag) puts("Yes");
    else puts("No");



    system("pause");
    return 0;
}

背包求具体方案

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const int N = 1010;
const int M = 2 * N;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int v[N],w[N];
int f[N][N];
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = n; i >= 1; i --)
    {
        for(int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j],f[i + 1][j - v[i]] + w[i]);
        }
    }
    int j = m;
    for(int i = 1; i <= n; i ++)
    {
        if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << ' ';
            j -= v[i];
        }
        else continue;
    }

}
int main()
{

    solve();



    system("pause");
    return 0;
}