图

图

求解最短路径

时间复杂度 空间复杂度

• 单源最短路径
• 多源最短路径
• 条数最短（点权为1）
• 边权之和最小或最大（花费之和）
• 点权之和最小或最大

多源最长路径（DAG）（关键路径）

深度遍历

  void dfs(int cur,int dst){
        if(minpath<dst) return;//当前走过的路径大雨之前的最短路径，没有必要再走下去了
        if(cur==en){//临界条件，当走到终点n
           if(minpath>dst){ minpath=dst; return;  }
        }
        for(int i=1;i<=n;i++){
            if(mark[i]==0&&edge[cur][i]!=inf&&edge[cur][i]!=0){
                mark[i]=1;
                dfs(i,dst+edge[cur][i]);
                mark[i]=0;//需要在深度遍历返回时将访问标志置0
            }
         }
         return;
    }

bellman-ford

for(k=1;k<=n-1;k++)  //外循环循环n-1次，n为顶点个数
    for(i=1;i<=m;i++)//内循环循环m次，m为边的个数，即枚举每一条边
        if(dis[v[i]]>dis[u[i]]+w[i])//尝试对每一条边进行松弛，与Dijkstra算法相同
            dis[v[i]]=dis[u[i]]+w[i]; 

例子：1003 Emergency (25 分)

1.以深度优先为基础

• 在递归函数变量上加上边权/点权这一步改变之后的运算（或者用全局变量，则在递归函数前后写上改变前后的运算，达到一样的效果）
• 求最大最小边权点权的个数的话只能启用数组

#include <iostream>
using namespace std;

const int MAX=500;
const int INF=10000000;
int countMax=0,maxTeam[500]={0},c2Profile[500]={INF},k=0,targetProfile=INF,targetTeam=0;
void DFS(int N,int profile[][MAX],int c1,int c2,int c[],int visited[],int team,int minProfile) {

    if(c1==c2){
        maxTeam[k]=team;
        if(targetProfile>minProfile)
            targetProfile=minProfile;
        c2Profile[k]=minProfile;
        k++;
//        cout<<"-"<<team<<endl;
        return;
    }

    visited[c1]=1;
    for (int i = 0; i < N; i++) {
        if (profile[c1][i]!= 0&&visited[i]!=1){
            visited[i]=1;
//            cout<<"--"<<team<<"+"<<c[i]<<endl;
//           cout<<i<<"~"<<minProfile<<"~"<<c1<<endl;
            DFS(N, profile, i,c2,c,visited,team + c[i],minProfile + profile[c1][i]);
            visited[i]=0;
        }
    }
}

int main() {
    int N,M,C1,C2,c1,c2,l;

    int c[MAX],visited[MAX]={0};
    int profile[MAX][MAX];

    cin >> N >> M >> C1 >> C2;
    for(int i=0;i<N;i++)
        cin >> c[i];

    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            profile[i][j]=0;

    for(int j=0;j<M;j++){
        cin >> c1 >> c2 >> l;
        profile[c1][c2]=l;
        profile[c2][c1]=l;
    }

    DFS(N, profile, C1,C2,c,visited,0,0);

    for(int i=0;i<k;i++)
        if(c2Profile[i]==targetProfile) {
            countMax++;
            if(targetTeam<maxTeam[i])
                targetTeam=maxTeam[i];
        }
    cout << countMax <<" "<< targetTeam+c[C1] <<endl;
    return 0;
}

2.使用dijkstra

• 不需要递归！！！
• 贪心的广度优先思想，把所有点的dist（最短边权）组成集合选出最小值（包括初始点），对这个点周围的所有相关边进行松弛（更新dist）
• 条数与点权在此基础上完成
• 无法求负边权

时间复杂度 O(V²)

#include <iostream>

using namespace std;

const int MAX = 500;
const int INF = 10000000;
int N, M, C1, C2, c1, c2, l;
int numPath[500] = {0}, maxTeam[500] = {0};

void Dijkstra(int profile[][MAX], int dist[], int visited[], const int team[]) {
    int min = 0, minPath = INF;
    dist[C1] = 0;
    numPath[C1] = 1;
    maxTeam[C1] = team[C1];
    for (int i = 0; i < N; i++) {
        if (profile[C1][i] != 0) {
            dist[i] = profile[C1][i];
        }
//        cout << dist[i] << endl;
    }
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++)
            if (visited[i] == 0 && dist[i] < minPath) {
                minPath = dist[i];
//                maxTeam[i] = team[i];
                min = i;
            }
//        cout << "+" << min << " " << minPath << endl;
        if (min == INF) break;
        visited[min] = 1;
        for (int i = 0; i < N; i++) {
            if (profile[min][i] != 0 && dist[i] > dist[min] + profile[min][i]) {
                dist[i] = dist[min] + profile[min][i];
                numPath[i] = numPath[min];
                maxTeam[i] = maxTeam[min] + team[i];
//                cout << "-" << i << " " << dist[min] << " " << numPath[i] << " " << maxTeam[i] << endl;
            } else if (profile[min][i] != 0 && dist[i] == dist[min] + profile[min][i]) {
                numPath[i] = numPath[i] + numPath[min];
                if (maxTeam[i] < maxTeam[min] + team[i])
                    maxTeam[i] = maxTeam[min] + team[i];
//                cout << "~" << i << " " << numPath[i] << " " << maxTeam[i] << endl;
            }
        }
        minPath = INF;
    }
}

int main() {
    int team[MAX] = {0}, dist[MAX], visited[MAX] = {0};
    int profile[MAX][MAX];

    cin >> N >> M >> C1 >> C2;
    for (int i = 0; i < N; i++)
        cin >> team[i];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            profile[i][j] = 0;
        dist[i] = INF;
//        cout<<dist[i]<<endl;
    }

    for (int j = 0; j < M; j++) {
        cin >> c1 >> c2 >> l;
        profile[c1][c2] = l;
        profile[c2][c1] = l;
    }

    Dijkstra(profile, dist, visited, team);

    cout << numPath[C2] << " " << maxTeam[C2] << endl;
    return 0;
}

3.使用bellman-ford

• 处理负边权

时间复杂度 O(VE)

4.使用SPFA

• 不推荐

连通图-拓扑

无向图

1.连通：检查连通分支（相连的点的一个小团体）个数

• 是否连通：连通分支个数=1，则连通；>1，不连通
• 缺几条边构成连通：缺边数=通分支个数-1
  e.g畅通工程：

并查集

2.求桥

• 什么是桥：在一个无向图中，如果去掉一条边，使得图被分成了几个部分，那么这条边就被称为桥。

有向图

离散定义

• 单向连通一定是弱连通的。but，弱连通不一定是单向连通~~

1.强连通

• tarjan时间戳：### 全网最!详!细!tarjan算法讲解 - K键盘里的青春K - CSDN博客

tarjan(u){
　　DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
　　Stack.push(u)   // 将节点u压入栈中
　　for each (u, v) in E // 枚举每一条边
　　　　if (v is not visted) // 如果节点v未被访问过
　　　　　　　　tarjan(v) // 继续向下找
　　　　　　　　Low[u] = min(Low[u], Low[v])
　　　　else if (v in S) // 如果节点u还在栈内
　　　　　　　　Low[u] = min(Low[u], DFN[v])
　　if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
　　repeat v = S.pop  // 将v退栈，为该强连通分量中一个顶点(下三句即打印栈内所有元素)
　　print v
　　until (u== v)
}

• kosaraju
  
  to-do：证明还不是很会，搞不懂为什么一定是 最早时间戳+转置图 的组合
• poj 2186 Popular Cows

2.弱连通

3.半连通

给定有向图 G = (V, E) ，如果对于所有结点对u，v ∈ V，我们有u→v或v→u,则G是半连通的。请给出一个有效的算法来判断图G是否半连通的。证明算法正确性并分析运行时间。

• 先强连通缩点，再拓扑求单链
• 先判断是否是连通，再判断是否是单连通。
• 引理：有向无环图G(V,E)，G是半连通的当且仅当有一条路径，这条路径上有图G中所有点。（可证）
  e.g. [Going from u to v or from v to u?]POJ - 2762

4.单连通

对于有向图 G = (V, E) 来说，如果 u ~> v 意味着图 G 包含一条从 u 到 v 的简单路径，则图 G 是单连通图。请给出一个有效算法来判断一个有向图是否单连通图。

• 八会

-to be continued