树的重心

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #define rep(x,y) for(ull i = (x);i<=(y);i++)
  5. using namespace std;
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef pair<ll,ll> pii;
  9. const int maxn = 1e6+10;
  11. int N,a,b;
  12. int res = maxn;//初始化为最大值
  13. int e[maxn],h[maxn],ne[maxn],idx;//使用数组模拟的方式来做，速度快一倍
  14. bool vis[maxn];//访问标记数组
  15. void add(int a,int b){ //头插法加边
  16.     e[idx] = b;
  17.     ne[idx] = h[a];
  18.     h[a] = idx++;
  19. }
  20. //返回u子树的结点个数
  21. int DFS(int u){
  22.     vis[u] = 1;//添加已经访问了
  23.     int sum = 1,m = 0; //sum计算u子树的总结点数,m记录把s结点删除后，个联通分量最大的结点数
  24.     for(int i = h[u];i!=-1;i = ne[i]){
  25.         int j = e[i];
  26.         if(!vis[j]){
  27.             int s = DFS(j);
  28.             sum+=s;
  29.             m = max(m,s);
  30.         }
  31.     }
  32.     m = max(m,N-sum);//计算除了u子树以外的联通分量
  33.     res = min(res,m);//更新最小值
  34.     return sum;
  35. }
  37. int main(){
  38.     memset(h,-1,sizeof h);
  39.     cin>>N;
  40.     rep(1,N){
  41.         cin>>a>>b;
  42.         add(a,b);
  43.         add(b,a);
  44.     }
  45.     DFS(1);
  46.     cout<<res;
  47.     return 0;
  48. }

拓扑排序

#include <iostream>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <bitset>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int maxn = 1e6+10;

int N,M,a,b;
int h[maxn],e[maxn],ne[maxn],idx;//使用数组模拟邻接表
int cnt[maxn]; //记录每个点的入度数量
int q[maxn],hh = 0,tt = -1;//使用数组模拟队列，可以记录下入队顺序，速度还快
void add(int a,int b){ //头插法插入一条边
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

void topsort(){ //拓扑排序
    for(int i = 1;i<=N;i++){ //先放入入度为0的点
        if(cnt[i] == 0) q[++tt] = i;
    }
    while(hh<=tt){
        int t = q[hh++];
        for(int i = h[t];i!=-1;i = ne[i]){
            int j = e[i];
            cnt[j]--;
            if(cnt[j] == 0){ //实时判断是否有新的入度为0的点
                q[++tt] = j;
            }
        }
    }
    if(hh == N) //条件成立->所有点都入队出队了
        for(int i = 0;i<hh;i++) cout<<q[i]<<" "; //输入队的顺序
    else
        cout<<-1;
}

int main(){
    memset(h,-1,sizeof h);//初始化邻接表
    cin>>N>>M;
    rep(1,M){
        cin>>a>>b;
        add(a,b);
        cnt[b]++;
    }
    topsort();
    return 0;
}

最短路

基础图论问题 - 图1朴素的Dijkstra算法适用与稠密图,因为他只与点数有关
堆优化版的适用有稀疏图，如果用来处理稠密图时间复杂度会变成 O(n^2logn)
多源最短路：多次询问两点的最短距离
Bellman-Ford：可以处理要求不超过k条边的最短路问题
Bellman-Ford和SPFA可以在没有负环情况下求最短路问题，也可以判断一个图中是否存在负环，SPFA是Bellman-Ford的优化版，效率更高。
拓展：Dijkstra基于贪心，Ford基于动态规划

朴素Dijkstra算法

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3+10;

int N,M,a,b,w;
int G[maxn][maxn];
int vis[maxn],dis[maxn];

int Dijkstra(){ //循环点N次，循环边M次，时间复杂度O(N*M)
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;

    for(int i = 1;i<=N;i++){ // 循环N个顶点
        int s = -1;
        for(int j = 1;j<=N;j++){ //寻找当前已知的最短路径点，并且没有访问过
            if(!vis[j] && (s == -1 || dis[j] < dis[s]))
                s = j;
        }
        for(int j = 1;j<=N;j++){ //去更新已知最短点周围的点
            dis[j] = min(dis[j],dis[s]+G[s][j]);
        }
        vis[s] = 1;
    }
    if(dis[N] == 0x3f3f3f3f) return -1;
    return dis[N];
}

int main(){
    cin>>N>>M;
    memset(G,0x3f,sizeof G);
    while(M--){
        cin>>a>>b>>w;
        G[a][b] = min(G[a][b],w);//因为题目中说了会有重边，所以就保存最短的那一条即可
    }
    cout<<Dijkstra();
    return 0;
}

堆优化版的Dijkstra算法

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;

int N,M,a,b,c;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx;//头节点表，编号表，权值表，链表
bool vis[maxn];int dis[maxn];//访问标记数组，距离数组
priority_queue<pii,vector<pii>,greater<pii> > heap;//堆，用堆去找目前距离最短的点(未访问过)

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

int Dijkstra(){
    memset(dis,0x3f,sizeof dis);
    heap.push({0,1});//第一个是距离，第二个是编号
    dis[1] = 0;

    while(heap.size()){ 
        auto p = heap.top();heap.pop(); //找距离距离最短的点
        int d = p.first,s = p.second;
        if(vis[s]) continue;//如果已经访问过
        vis[s] = true;
        for(int i = h[s];i != -1;i = ne[i]){// i为地址
            int j = e[i]; //j是编号
            if(d+w[i] < dis[j]){
                dis[j] = d+w[i];
                heap.push({dis[j],j});
            }
        }
    }
    if(dis[N] == 0x3f3f3f3f) return -1;
    return dis[N];
}

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

    memset(h,-1,sizeof h);//初始化邻接表

    cin>>N>>M;
    while(M--){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<Dijkstra();
    return 0;
}

Bellman-Ford算法

可以处理含负权边的图，可以处理对最短路径有边数限制条件的情况(独有)
验证是否负权环：对每条边都进行松弛操作。之后如果还能有一条边能进行松弛，那么就返回False，否则算法返回True。(但一般判断负环因其时间复杂度比较高不用Bellman-Ford算法，二用SPFA算法)

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;

int N,M,K,a,b,c;//N个顶点，M条边，最短路径不能超过K条边
struct node{
    int a,b,w;
}edges[maxn];
int idx;
int dis[510],backup[510];//距离数组及其备份

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

    for(int i = 0;i<K;i++){
        memcpy(backup,dis,sizeof dis); //使用备份来更新，可以保证下面的for循环每次只会在原来路径上扩展一条边
                                        //如果不用备份， 那么可能更新中会出现最短路径边数大于K的情况
        for(int j = 0;j<M;j++){
            int a = edges[j].a,b = edges[j].b,w = edges[j].w;
            if(backup[a] == 0x3f3f3f3f) continue;//不能用无穷大来扩展路径
            dis[b] = min(dis[b],backup[a]+w);
        }
    }
    return dis[N] == 0x3f3f3f3f ? -1:dis[N];
}

int main(){
    cin>>N>>M>>K;
    rep(1,M){
        cin>>a>>b>>c;
        edges[idx++] = {a,b,c};
    }
    int r = bellman_ford();
    if(r!=-1) cout<<r;
    else cout<<"impossible";

    return 0;
}

SPFA

用于求最短路时间复杂度比Bellman-ford低

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;

int N,M,a,b,c;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx;
bool vis[maxn];
int dis[maxn];
queue<int> q;
void add(int a,int b,int c){
    e[idx] = b,w[idx] =c,ne[idx] = h[a],h[a] = idx++;
}

int SPFA(){ //思路：就是只有dis[t]+w[i] < dis[j]成立才去更新j周围的邻接点。
    memset(dis,0x3f,sizeof dis);
    q.push(1);
    vis[1] = 1;
    dis[1] = 0;

    while(q.size()){
        int t = q.front();q.pop();
        vis[t] = 0;
        for(int i = h[t];i!=-1;i = ne[i]){
            int j = e[i];
            if(dis[t]+w[i] < dis[j]){
                dis[j] = dis[t]+w[i];
                if(!vis[j]){ //因为队列中仅仅是保存结点编号，更新是在dis数组中，所以在队列中的编号就不用重复入队了
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }
    if(dis[N]!= 0x3f3f3f3f) return dis[N];
    return -1;
}
int main(){
    memset(h,-1,sizeof h);

    cin>>N>>M;
    rep(1,M){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int r = SPFA();
    if(r == -1) cout<<"impossible";
    else cout<<r;

    return 0;
}

SPFA算法判断图是否有负环

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;

int N,M,a,b,c;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx;
bool vis[maxn];
int dis[maxn],cnt[maxn];
queue<int> q;
void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

int SPFA(){ 
    rep(1,N) q.push(i),vis[i] = 1;
    while(q.size()){
        int t = q.front();q.pop();
        vis[t] = 0;
        for(int i = h[t];i!=-1;i = ne[i]){
            int j = e[i];
            if(dis[t]+w[i] < dis[j]){
                dis[j] = dis[t]+w[i];
                cnt[j] = cnt[t]+1;
                if(cnt[j]>=N) return 1; //基于抽屉原理，如果没有负环最长的边为N-1，而更新是变小，N条边的路径说明有两个
                                        //点是同一个点，说明有负权环
                if(!vis[j]){
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    memset(h,-1,sizeof h);

    cin>>N>>M;
    rep(1,M){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int r = SPFA();
    if(r) cout<<"Yes";
    else cout<<"No";

    return 0;
}

floyd算法

#include <iostream>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <bitset>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define rep2(x,x2,y,y2,G) for(ull i = (x);i<=(x2);i++) {for(ull j = (y);j<=(y2);j++) cout<<G[i][j]<<" ";cout<<endl;}
#define pb push_back
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double,string> pii;
const int maxn = 1e6+10;
const int P = 131;
const int inf = 0x3f3f3f3f;
int dir8[8][2] = {1,1,1,-1,-1,1,-1,-1,1,0,0,1,-1,0,0,-1};
int dir4[4][2] = {0,1,1,0,0,-1,-1,0};


int N,M,K,a,b,c;
int G[210][210];

void floyd(){ //基于动态规划，类似于离散数学中的wallshall算法
    for(int k = 1;k<=N;k++)
        for(int i = 1;i<=N;i++)
            for(int j = 1;j<=N;j++)
                G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
}

int main(){
    cin>>N>>M>>K;

    for(int i = 1;i<=N;i++) //初始化点到点的距离
        for(int j = 1;j<=N;j++)
            if(i == j) G[i][j] = 0;
            else G[i][j] = inf;

    while(M--){
        cin>>a>>b>>c;
        G[a][b] = min(G[a][b],c);
    }
    floyd();

    while(K--){
        cin>>a>>b;
        if(G[a][b] > inf/2) cout<<"impossible\n";//因为有负权边
        else cout<<G[a][b]<<endl;
    }

    return 0;
}

最小生成树

image.png
边权正负都可以
堆优化版堆prim用的特别少，不用掌握
朴素版prime用于稠密图，kruskal用于稀疏图

prim算法

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;

int N,M,a,b,c;
int G[maxn][maxn],dis[maxn];
bool vis[maxn];
int prim(){
    memset(dis,0x3f,sizeof dis);
    int res  = 0;//最小生成树的权值和
    for(int i = 0;i<N;i++){
        int t = -1;
        for(int j = 1;j<=N;j++){
            if(!vis[j] && (t == -1 || dis[j] < dis[t])){
                t = j;
            }
        }
        if(i && dis[t] == inf) return inf;//第一次的结点距离不用算，所以跳过第一次，也就是i==0的时候
        if(i) res+=dis[t]; //第一次的距离不用加
        vis[t] = true;
        for(int j = 1;j<=N;j++) dis[j] = min(dis[j],G[t][j]); //用新加入的点去更新其他点
    }
    return res;
}

int main(){

    memset(G,0x3f,sizeof G);

    cin>>N>>M;
    while(M--){
        cin>>a>>b>>c;
        G[a][b] = G[b][a] = min(G[a][b],c);
    }

    int r = prim();
    if(r == inf) cout<<"impossible\n";
    else cout<<r<<endl;

    return 0;
}

克鲁斯卡尔算法

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int inf = 0x3f3f3f3f;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;


int N,M,a,b,w;//N:点数 M:边数
int fa[maxn];
struct edge{
    int a,b,w;
    bool operator <(const edge& other) const{
        return w<other.w;
    }
}edges[maxn];

int find(int x){
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx!=fy) fa[fx] = fy;
}
int main(){
    cin>>N>>M;

    rep(1,N) fa[i] = i;//并查集初始化
    rep(0,M-1){
        cin>>a>>b>>w;
        edges[i] = {a,b,w};
    }
    sort(edges,edges+M);
    int res = 0,cnt = 0;
    for(int i = 0;i<M;i++){
        a = edges[i].a,b = edges[i].b,w = edges[i].w;
        if(find(a) != find(b)){ //是否联通
            join(a,b);
            res+=w;//生成树的权值和
            cnt++;//边的计数
        }
    }
    if(cnt!=N-1) cout<<"impossible\n"; //最小生成树的边为N-1
    else cout<<res<<endl;
    return 0;
}

二分图

image.png
一个图是二分图当且仅当图中不含奇数环

二分图判定算法

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int inf = 0x3f3f3f3f;
int dir8[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir4[4][2] = {0,1,1,0,0,-1,-1,0};
char dir4show[4] = {'r','d','l','u'};
const double eps = 1e-6;

int T,N,M,a,b;
bool ok;
vector<int> h[2100];
int col[2100];

//用0和1来染色
void DFS(int s){ //用DFS来染色会比BFS速度快很多
    if(!ok) return ;
    for(int i = 0;i<h[s].size();i++){
        int j = h[s][i];
        if(col[j] == -1){
            col[j] = col[s]^1;//染和s结点相反的颜色
            DFS(j);
        }else if(col[j] == col[s]){ //如果已经和结点s颜色相同了，那么必定不是二分图
            ok = false;
            return;
        }
    }
}
int main(){
    scanf("%d",&T);
    int kase = 0;
    while(T--){
        printf("Scenario #%d:\n",++kase);
        cin>>N>>M;
        memset(col,-1,sizeof col);//初始化染色标记数组
        for(int i = 1;i<=N;i++) h[i].clear();//清空邻接表
        ok = true;
        while(M--){
            scanf("%d%d",&a,&b);
            h[a].pb(b);
            h[b].pb(a);
        }

        for(int i = 1;i<=N && ok;i++){ //对每个未染色点都进行DFS，因为可能有多个联通分量
            if(col[i] == -1){
                col[i] = 0;
                DFS(i);
            }
        }
        if(ok) printf("No suspicious bugs found!\n");
        else printf("Suspicious bugs found!\n");
        if(T) puts("");
    }

    return 0;
}

匈牙利算法

主要就是解决二分图最大匹配问题

#include <iostream>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <bitset>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);i++)
#define rep2(x,x2,y,y2,G) for(ull i = (x);i<=(x2);i++) {for(ull j = (y);j<=(y2);j++) cout<<G[i][j]<<" ";cout<<endl;}
#define pb push_back
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double,string> pii;
const int maxn = 1e6+10;
const int P = 131;
const int inf = 0x3f3f3f3f;
int dir8[8][2] = {1,1,1,-1,-1,1,-1,-1,1,0,0,1,-1,0,0,-1};
int dir4[4][2] = {0,1,1,0,0,-1,-1,0};


int n1,n2,k,a,b;
int h[maxn],e[maxn],ne[maxn],idx;
int match[maxn];//妹子成功匹配的男生
bool st[maxn];//某个男生喜欢的妹子

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]; //j只会是x所喜欢的妹子
        if(!st[j]){ //如果x还没有尝试去争取j，就去尝试一下，要么j还没有匹配match，要么当前和j匹配好的男生可以找到下一家
            st[j] = true;
            if(match[j] == 0 || find(match[j])){
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    memset(h,-1,sizeof h);

    cin>>n1>>n2>>k;
    rep(1,k){
        cin>>a>>b;
        add(a,b);
    }
    int res  = 0;
    for(int i = 1;i<=n1;i++){ //遍历所有男生
        memset(st,false,sizeof st);//开始所有妹子都可以去争取
        if(find(i)) res++;//如果找到了，就匹配+1
    }
    cout<<res<<endl;
    return 0;
}