好嘞，接着学

　　欧拉回路，欧拉通路 get

　　链式前向星 get

　　与欧拉回路的对比：欧拉回路是指不重复地走过所有路径的回路；哈密尔顿回路是指不重复地走过所有点并且最后回到起点的回路。

　　笑死，csdn的编译器中 \geqslant 是>=

　　拓扑排序，AOV网 get

　　AOE网 get （并没看出来与aov网有什么不同

　　AOE AOV网不同可能在于存储方式

　　将无穷大设为 0x3f3f3f3f

　　floyd算法 get

　　floyd算法主体：

for(int k=1;k<=n;k++)//第一重循环为i→j的中间点k
    for(int i=1;i<=n;i++)//第二重循环为起点i
        for(int j=1;j<=n;j++)//第三重循环为终点j
            if(dis[i][j]>dis[i][k]+dis[k][j])//如果i→k的距离加上k→j的距离小于i→j的距离
                dis[i][j]=dis[i][k]+dis[k][j];//更新最短路径

　　搞几个板子（扭

　　floyd矩阵存入

　　

void floyd(int n) {
    for (int k = 1; k <= n; k++) {         //枚举中间点
        for (int i = 1; i <= n; i++) {     //枚举起点
            for (int j = 1; j <= n; j++) { //枚举终点
                if (G[i][k] < INF && G[k][j] < INF) {
                    if (G[i][j] > G[i][k] + G[k][j]) { //松弛操作
                        G[i][j] = G[i][k] + G[k][j];
                        path[i][j] = path[i][k]; //更新路径
                    } 
                    else if (
                        G[i][j] == G[i][k] + G[k][j] && path[i][j] > path[i][k]) { //在最短路相同的情况下，更新字典序最小的路径
                        path[i][j] = path[i][k]; //最终path中存的是字典序最小的路径
                    }
                }
            }
        }
    }
}

　　SPFA（标准版

void SPFA(int S) {
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[S] = 0;
 
    queue<int> Q;
    Q.push(S);
 
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        vis[x] = false;
        for (int i = head[x]; i != -1; i = edge[i].next) {
            int to = edge[i].to;
            if (dis[to] > dis[x] + edge[i].dis) {
                dis[to] = dis[x] + edge[i].dis;
                if (!vis[to]) {
                    vis[to] = true;
                    Q.push(to);
                }
            }
        }
    }
}

　　带负环判断的SPFA（扭

struct SPFA {
    int n, m;
    Edge edges[N]; //所有的边信息
    int head[N];   //每个节点邻接表的头
    int next[N];   //每个点的下一条边
    int pre[N];    //最短路中的上一条弧
    bool vis[N];
    int dis[N];
    int cnt[N]; //进队次数
 
    void init(int n) {
        this->n = n;
        this->m = 0;
        memset(head, -1, sizeof(head));
    }
 
    void AddEdge(int from, int to, int dist) {
        edges[m] = Edge(from, to, dist);
        next[m] = head[from];
        head[from] = m++;
    }
 
    bool negativeCycle(int s) { //判负环
        memset(vis, false, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;
 
        queue<int> Q;
        Q.push(s);
 
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = false;
            for (int i = head[x]; i != -1; i = next[i]) {
                Edge &e = edges[i];
                if (dis[e.to] > dis[x] + e.dis) {
                    dis[e.to] = dis[x] + e.dis;
                    pre[e.to] = i;
                    if (!vis[e.to]) {
                        vis[e.to] = true;
                        Q.push(e.to);
                        if (++cnt[e.to] > n)
                            return true;
                    }
                }
            }
        }
        return false;
    }
} spfa;

　　大概是存储板子（ww

struct Edge {
    int to, next;
    int dis;
} edge[N];
int head[N], tot;
bool vis[N];
int dis[N];
void addEdge(int x, int y, int dis) {
    edge[++tot].to = y;
    edge[tot].dis = dis;
    edge[tot].next = head[x];
    head[x] = tot;
}

　　9：47惹

　　Ford算法不看了，貌似能被SPFA概括？

　　Dijkstra 算法（矩阵存入

int G[N][N];//G[i][j]表示i到j的有向边长
bool vis[N];//表示w[i]是否已经计算完
void dijkstra(int n,int s){
    for(int i=1;i<=n;i++){
        int x;//x标记当前最短w的点
        int min_dis=INF;//记录当前最小距离
 
        for(int y=1;y<=n;y++){
            if(!vis[y] && min_dis>=dis[y]){
                x=y;
                min_dis=dis[x];
            }
        }
 
        vis[x]=true;
 
        for(int y=1;y<=n;y++) 
            dis[y]=min(dis[y],dis[x]+G[x][y]);
    }
}

　　我服了，咋那么多最短路算法。

　　传统美德

　　哦，没事了，下一节不是最短路

　　（呼

　　差分约束系统，看起来好难阿

　　看起来好神奇（思索

　　xswl，这个差分甚么的，不辍，但好像用不上 get

　　学到树了（好快啊

　　就是板子都还没背

　　累了，水一会儿（确信

　　10：08

　　最小生成树prim算法（适合稠密图 get

int n,m;//n个点m条边
int G[N][N];
int dis[N];
bool vis[N];
int MST;
void Prim(){
    for(int i=1;i<=n;i++){
        int k;
        int minn=INF;
        for(int j=1;j<=n;j++){//枚举所有点
            if(!vis[j]&&dis[j]<minn){//寻找与白点相连的权值最小的蓝点u
                minn=dis[j];
                k=j;
            }
        }
        vis[k]=true;//蓝点u加入生成树，标记为白点
        for(int j=1;j<=n;j++)//修改所有与u相连的蓝点
            if(!vis[j]&&dis[j]>G[k][j])
                dis[j]=G[k][j];
    }
 
    MST=0;
    for(int i=1;i<=n;i++)//权值和的计算
        MST+=dis[i];
}

　　最小生成树kruskal（适合稀疏图 get

struct Edge {
    int x, y;
    int dis;
    bool operator<(Edge K) const { return dis < K.dis; }
} edge[N];
int father[N];
int Find(int x) {
    if (father[x] == x)
        return x;
    return father[x] = Find(father[x]);
}
int kruskal(int n, int m) {
    for (int i = 1; i <= n; i++) //并查集初始化
        father[i] = i;
    sort(edge + 1, edge + m + 1); //升序排序
 
    int MST = 0;
    int edgeNum = 0; //边数
    for (int i = 1; i <= m; i++) {
        int x = Find(edge[i].x);
        int y = Find(edge[i].y);
        if (x != y) {
            father[x] = y;
            MST += edge[i].dis;
            edgeNum++;
        }
        if (edgeNum == n - 1) { // n-1条边时停止
            return MST;
        }
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].dis);
    int MST = kruskal(n, m);
    printf("%d\n", MST);
    return 0;
}

　　生成树计数(基尔霍夫矩阵 神奇！ get

LL K[N][N];
LL gauss(int n){//求矩阵K的n-1阶顺序主子式
    LL res=1;
    for(int i=1;i<=n-1;i++){//枚举主对角线上第i个元素
        for(int j=i+1;j<=n-1;j++){//枚举剩下的行
            while(K[j][i]){//辗转相除
                int t=K[i][i]/K[j][i];
                for(int k=i;k<=n-1;k++)//转为倒三角
                    K[i][k]=(K[i][k]-t*K[j][k]+MOD)%MOD;
                swap(K[i],K[j]);//交换i、j两行
                res=-res;//取负
            }
        }
        res=(res*K[i][i])%MOD;
    }
    return (res+MOD)%MOD;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(K,0,sizeof(K));
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        K[x][x]++;
        K[y][y]++;
        K[x][y]--;
        K[y][x]--;
    }
    printf("%lld\n",gauss(n));
    return 0;
}

　　最小生成树计数（加强版

struct Edge {
    int x,y;
    int dis;
    bool operator < (const Edge &rhs) const {
        return dis<rhs.dis;
    }
} edge[N],tr[N];
int n,m;
int father[N];
int G[N][N];
int tot,bel[N],val[N];
int Find(int x) {
    if(father[x]!=x)
        return father[x]=Find(father[x]);
    return x;
}
int Gauss(int n) {
    int res=1;
    for(int i=1; i<=n; i++) {
        for(int k=i+1; k<=n; k++) {
            while(G[k][i]) {
                int d=G[i][i]/G[k][i];
                for(int j=i; j<=n; j++)
                    G[i][j]=(G[i][j]-1LL*d*G[k][j]%MOD+MOD)%MOD;
                swap(G[i],G[k]);
                res=-res;
            }
        }
        res=1LL*res*G[i][i]%MOD,res=(res+MOD)%MOD;
    }
    return res;
}
int Kruskal() {
    sort(edge+1,edge+m+1);
    for(int i=1; i<=n; i++)
        father[i]=i;
    int cnt=0;
    for(int i=1; i<=m; i++) {
        int fu=Find(edge[i].x);
        int fv=Find(edge[i].y);
        if(fu==fv)
            continue;
        father[fu]=fv,tr[++cnt]=edge[i];
        if(edge[i].dis!=val[tot])
            val[++tot]=edge[i].dis;
    }
    return cnt;
}
void addTreeEdge(int v) {
    for(int i=1; i<n&&tr[i].dis!=v; i++){
        int x=tr[i].x;
        int y=tr[i].y;
        father[Find(x)]=Find(y);
    }
    for(int i=n-1; i&&tr[i].dis!=v; i--){
        int x=tr[i].x;
        int y=tr[i].y;
        father[Find(x)]=Find(y);
    }
}
void rebuild(int v) {
    memset(G,0,sizeof(G));
    for(int i=1; i<=m; i++){
        if(edge[i].dis==v){
            int x=bel[edge[i].x];
            int y=bel[edge[i].y];
            G[x][y]--;
            G[y][x]--;
            G[x][x]++;
            G[y][y]++;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);
 
    int cnt=Kruskal();
    if(cnt!=n-1) {
        printf("0\n");
    }
    else{
        int res=1;
        for(int i=1; i<=tot; i++) {
            for(int i=1; i<=n; i++)
                father[i]=i;
 
            addTreeEdge(val[i]);
 
            int blo=0;
            for(int i=1; i<=n; i++)
                if(Find(i)==i)
                    bel[i]=++blo;
            for(int i=1; i<=n; i++)
                bel[i]=bel[Find(i)];
 
            rebuild(val[i]);
            res=1LL*res*Gauss(blo-1)%MOD;
        }
        printf("%d\n",res);
    }
    return 0;
}

　　矩阵的行列式......不想学ww，看到定义就头大（眨眼

　　yysy，看完了，看懂啦，也不知能记住几天

　　头大

　　曼哈顿距离最小生成树 没看懂 我服了 看不进去

　　爬去调调今天集训的题了