一.深度優(yōu)先搜索的剪枝

1.可行性剪枝
下面的算法用于從0~30個數(shù)中選取8個末荐，使其和為200.每一個數(shù)有選與不選兩個枝，若選取得數(shù)字個數(shù)已經(jīng)大于8個翎冲，將這個枝剪去君编，若數(shù)字和s已經(jīng)大于200，則將這個枝剪去尊蚁。
這種判斷解是否可行得剪枝稱位可行性剪枝亡笑。

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s) {
    if(cnt>k){
        return;
    }
    if(s>sum){
        return;
    }
    if (i == n) {
        if (cnt == k && s == sum) {
            ans++;
        }
        return;
    }
    dfs(i + 1, cnt, s);
    dfs(i + 1, cnt + 1, s + a[i]);
}
int main() {
    n = 30;
    k = 8;
    sum = 200;
    for (int i = 0; i < 30; i++) {
        a[i] = i + 1;
    }
    ans = 0;
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

2.最優(yōu)性剪枝
這是尋找地圖中起點(diǎn)到終點(diǎn)最短路徑的算法
ans用于存儲目前最小的步數(shù)，如果某一條路徑長度(step)已經(jīng)大于ans了横朋，就將這條枝剪去仑乌，這樣尋找最優(yōu)解決辦法的剪枝叫做最優(yōu)性剪枝。若到達(dá)終點(diǎn)時步數(shù)小于ans，則更新ans的大小绝骚。

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int n,m;
string maze[110];
bool vis[110][110];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int ans=100000;
bool in(int x,int y){
    return 0<=x&&x<n&&0<=y&&y<m;
}
void dfs(int x,int y,int step){
    if(step>=ans){
        return;
    }
    if(maze[x][y]=='T'){
        ans=step;
        return;
    }
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){
            dfs(tx,ty,step+1);
        }
    }
    vis[x][y]=0;
}
int main() {
    cin>>n>>m;
    for(int i=0;i<n;++i){
        cin>>maze[i];
    }
    int x,y;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j]=='S'){
                x=i,y=j;
            }
        }
    }
    dfs(x,y,0);
    cout<<ans<<endl;
    return 0;
}

3.重復(fù)性剪枝
在與順序無關(guān)的深搜中耐版，我們最常用到重復(fù)性剪枝，例如從n個整數(shù)里選k個數(shù)使得和為s压汪。這種與順序無關(guān)的dfs中我們常用重復(fù)性剪枝粪牲。

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
void dfs(int s, int cnt,int pos) {
    if(s>sum||cnt>k){
        return;
    }
    if (s == sum && cnt == k) {
        ans++;
    }
    for (int i = pos; i < n; i++) {
        if (!xuan[i]) {
            xuan[i] = 1;
            dfs(s + a[i], cnt + 1,i+1);
            xuan[i] = 0;
        }
    }
}
int main() {
    n = 30;
    k = 8;
    sum = 200;
    for (int i = 0; i < 30; i++) {
        a[i] = i + 1;
    }
    ans = 0;
    dfs(0, 0,0);
    cout << ans << endl;
    return 0;
}

4.奇偶性剪枝
本質(zhì)上來說是一種可行性剪枝
從起點(diǎn)到終點(diǎn)，要求正好T步可以到達(dá)
設(shè)某一點(diǎn)得橫坐標(biāo)與縱坐標(biāo)之和為奇書就是白色止剖，偶數(shù)就是黑色腺阳。易得如果起點(diǎn)與終點(diǎn)同色，則必須走偶數(shù)步穿香，不同色則必須走奇數(shù)步亭引。可以根據(jù)這個奇偶性對結(jié)果進(jìn)行剪枝皮获。

#include <iostream>
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];
bool vis[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool ok;
void dfs(int x,int y,int t){
    if(ok)return;
    if(t==T){
        if(mat[x][y]=='D')ok=true;
        return;
    }
    vis[x][y]=true;
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<0||tx>=n||ty<0||ty>=m||mat[tx][ty]=='X'||vis[tx][ty])
            continue;
        dfs(tx,ty,t+1);
    }
    vis[x][y]=false;
}
int main() {
    cin >> n >> m >> T;
    for (int i = 0; i < n; ++i) {
        cin >> mat[i];
    }
    int sx,sy,ex,ey;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mat[i][j]=='S')sx=i,sy=j;
            if(mat[i][j]=='D')ex=i,ey=j;
        }
    }
    if((sx+sy+ex+ey+T)%2!=0){
        cout<<"NO"<<endl;
    }else{
        ok=false;
        dfs(sx,sy,0);
        if(ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

dfs剪枝習(xí)題

1.給一個數(shù)n焙蚓，要求你找出一個只由0和1組成的得十進(jìn)制數(shù)m，使這個正整數(shù)m可以被n整除洒宝。

#include <iostream>
#include <stdio.h>
using namespace std;
int n;
long long ans;
bool flag=false;
void dfs(long long num,int depth){
    if(flag||depth>18)return;//最優(yōu)性剪枝
    if(num%n==0){
        ans=num;
        flag=true;
        return;
    }
    dfs(num*10,depth+1);
    dfs(num*10+1,depth+1);
}

int main(){
    cin>>n;
    dfs(1,1);
    cout<<ans<<endl;
    return 0;
}

2.全排列
給出一個數(shù)n购公，輸出n的全排列的排列個數(shù)，并按字母序輸出

#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#define numToChar(x) (x+'0')
using namespace std;
int n;
bool vis[10];
vector<string> save;
void dfs(int num,string ans,int step){
    ans+=numToChar(num);
    if(step==n){
        save.push_back(ans);
        return;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,ans,step+1);
            vis[i]=false;
        }
    }
}

int main(){
    memset(vis,0,sizeof(vis));
    cin>>n;
    for(int i=1;i<=n;++i){
        vis[i]=true;
        dfs(i,"",1);
        vis[i]=false;
    }
    cout<<save.size()<<endl;
    for(int i=0;i<save.size();++i){
        printf("%s\n",save[i].c_str());
    }
    return 0;
}

3.蒜頭君的旅游計劃

#include <iostream>
#include <cstring>
using namespace std;
int n,ans=150010;
int mat[16][16];
bool vis[16];
void dfs(int city,int num,int money){
    if(num==n){
        ans=min(ans,money+mat[city][0]);
        return;
    }
    if(money>=ans)return;//最優(yōu)性剪枝
    for(int i=1;i<n;++i){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,num+1,money+mat[city][i]);
            vis[i]=false;
        }
    }
}

int main(){
    memset(vis,0,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>mat[i][j];
        }
    }
    dfs(0,1,0);
    cout<<ans<<endl;
    return 0;
}

4.正方形

#include <iostream>
#include <cstring>
using namespace std;
int sum=0;
int n,mat[30];
bool vis[30];
bool flag=false;
void dfs(int index,int cnt,int len){
    if(flag||len>(sum/4))return;
    if(cnt==3){
        flag=true;
        return;
    }
    if(len==sum/4){
        len=0;
        cnt++;
        index=0;
    }
    for(int i=index;i<n;++i){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,cnt,len+mat[i]);
            vis[i]=false;
        }
    }
}

int main(){
    memset(vis,0,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>mat[i];
        sum+=mat[i];
    }//搜索出四個長度相同的木棒
    bool f1=true;
    for(int i=0;i<n;++i){
        if(mat[i]>sum/4)f1=false;
    }
    if(sum%4==0&&f1)dfs(0,0,0);
    flag?cout<<"Yes":cout<<"No";
    return 0;
}

二雁歌，圖

當(dāng)邊的個數(shù)時宏浩，我們稱其為稀疏圖，反之為稠密圖靠瞎。無向圖中每一對頂點(diǎn)間相連叫完全圖比庄，在有向圖中任何一對頂點(diǎn)間都有兩條邊，則稱為有向完全圖乏盐。

度的概念

在無向圖中佳窑，頂點(diǎn)的度指某個頂點(diǎn)連出的邊數(shù)。
把圖中所有頂點(diǎn)的排列成一個序列s丑勤，s稱位一個度序列华嘹。圖中的邊數(shù)為總度數(shù)的一半。
在有向圖中法竞，和度對應(yīng)的有入度和出度兩個概念，入度指以該頂點(diǎn)為終點(diǎn)的有向邊數(shù)量强挫，出度指以該頂點(diǎn)為起點(diǎn)的有向邊數(shù)量岔霸。且總的入度數(shù)=總的出度數(shù)

一個度序列是否可圖，可以運(yùn)用Havel-Hakimi定理：
s:d1,d2,d3,d4,d5....dn可圖俯渤，那么d2-1,d3-1,d4-1,d5-1,....d(d1)-1.....dn可圖....

證明:4 3 2 2 1可圖
--->2 1 1 0
--->0 0 0 所以4 3 2 2 1可圖

核心代碼：

bool Havel_Hakimi(){
    for(int i=0; i<n-1; ++i){
        sort(arr+i,arr+n,greater<int>());
        if(i+arr[i] >= n) return false;
        for(int j=i+1; j<=i+arr[i] ; ++j){
            --arr[j];
            if(arr[j] < 0) return false;
        }
    }
    if(arr[n-1]!=0) return false;
    return true;
}

圖的存儲方法

1.鄰接矩陣存儲圖的例題:找朋友
G[i][j]=1代表i到j(luò)存在一條有向邊

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int G[6][6];
    memset(G,0,sizeof(G));
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        G[a][b]=1;
    }
    for(int i=1;i<=5;i++){
        int sum=0;
        for(int j=1;j<=5;j++){
            if(G[i][j]==1&&G[j][i]==1){
                sum++;
            }
        }
        cout<<i<<" 有 "<<sum<<" 個真正的朋友呆细。"<<endl;
    }
    return 0;
}

2.鄰接表
對于每一個頂點(diǎn)a，都用一個vector存儲a到b的有向邊
具體操作:G[a].push_back(b)
鄰接表的好處是存儲稀疏圖時比較省空間八匠，但是查詢起來效率較低絮爷。
在稀疏圖中我們常用鄰接表趴酣，稠密圖我們常用鄰接矩陣。
3.帶權(quán)值的圖的存儲方法
1）鄰接矩陣 G[a][b]存儲a到b的邊權(quán)
2）鄰接表 用一個struct存儲

#include <iostream>
#include <vector>
using namespace std;
struct node{
    int v,w;
};
vector<node> G[11];
void insert1(int u,int v,int w){
    node temp;
    temp.v=v;
    temp.w=w;
    G[u].push_back(temp);
}
void insert2(int u,int v,int w){
    insert1(u,v,w);
    insert1(v,u,w);
}
void input(){
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        insert2(u,v,w);
    }
}
int main() {
    
    return 0;
}

基于鏈表的鄰接表：

const int M = 1000000;
const int N = 10000;
struct edge {
    int v, d, next;
} e[M];
int p[N], eid;
void init() {  // 初始化坑夯，在建圖之前必須進(jìn)行
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int d) {  // 插入單向邊
    e[eid].v = v;
    e[eid].d = d;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int d) {  // 插入雙向邊
    insert(u, v, d);
    insert(v, u, d);
}
void output(int n) {  // 輸出整張圖中的所有邊
    for (int i = 0; i < n; i++) {
        for (int j = p[i]; j != -1; j = e[j].next) {  // 遍歷從 i 連出的所有邊
            cout << i << "->" << e[j].v << ", " << e[j].d << endl;
        }
    }
}

關(guān)系查詢：

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
int n,m;
map<string,vector<string>> friends;

int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        string temp1,temp2;
        cin>>temp1>>temp2;
        friends[temp1].push_back(temp2);
        friends[temp2].push_back(temp1);
    }
    cin>>m;
    for(int i=0;i<m;++i){
        string temp1,temp2;
        cin>>temp1>>temp2;
        bool flag=false;
        for(int j=0;j<friends[temp1].size();++j){
            if(friends[temp1][j]==temp2){
                flag=true;
                break;
            }
        }
        flag?cout<<"Yes"<<endl:cout<<"No"<<endl;
    }
    return 0;
}

蒜頭君的旅行計劃

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int n,m;
struct node{
    int pos,w;
};
bool vis[50000];
vector<vector<node>> e;
void play(int pos){
    if(vis[pos]){
        return;
    }
    vis[pos]=true;
    printf("%d ",pos);
    int m=1000010,index=-1;
    for(int i=0;i<e[pos].size();++i){
        if(e[pos][i].w<m){
            index=e[pos][i].pos;
            m=e[pos][i].w;
        }else if(e[pos][i].w==m)index=min(index,e[pos][i].pos);
    }
    play(index);
}

int main(){
    int u,v,w;
    cin>>n>>m;
    e.resize(n+1);
    for(int i=0;i<m;++i){
        scanf("%d %d %d",&u,&v,&w);
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    play(1);
    return 0; 
}

圖習(xí)題

1.完全圖的判定

#include <iostream>
using namespace std;
int n,m;

int main(){
    cin>>n>>m;
    bool e[110][110];
    int cnt=0;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        if(!e[u][v]){
            e[u][v]=e[v][u]=true;
            cnt++;
        }
    }
    if(cnt==n*(n-1)/2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

三岖寞、最短路

由于dfs解決最短路問題非常麻煩，而bfs只能解決權(quán)值為1的最短路柜蜈，所以我們引入了最短路算法仗谆。

1.Dijkstra

Dijkstra用于解決單源最短路問題，特點(diǎn)是以起點(diǎn)為中心淑履，逐層向外擴(kuò)展隶垮，值得注意的是，這個算法不能處理負(fù)邊秘噪。(bfs+貪心)
算法步驟
首先初始化一個dist[v]集合狸吞，它代表起點(diǎn)s到頂點(diǎn)v的距離，將起點(diǎn)s的dist初始化為0指煎，其他頂點(diǎn)置為inf
1.找出一個離源點(diǎn)最近的v蹋偏，將v加入最短路集合U
2.用dist[v]和v連出來的邊更新不在集合U的頂點(diǎn)，這一步稱為松弛操作
3.不停重復(fù)1贯要，2暖侨，直到V=U或者找不到新的點(diǎn)
如果V!=U，則說明找不到最短路徑崇渗，否則dist[i]代表s到i的最短路徑
算法演示：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, fail;
    edge() {}
    edge(int _v, int _w, int _fail) {
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M << 1];
int head[N], len;
void init() {
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
void add2(int u, int v, int w) {
    add(u, v, w);
    add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;//初始化
    for (int i = 0; i < n; ++i) {
        int mi = inf;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] < mi) {
                mi = dis[u = j];//尋找最近的未加入集合U的頂點(diǎn)
            }
        }
        if (mi == inf) {
            return;
        }
        vis[u] = true;
        for (int j = head[u]; ~j; j = e[j].fail) {//若找到字逗，對所有與這個點(diǎn)相連并且未訪問過的頂點(diǎn)進(jìn)行松弛
            int v = e[j].v;
            int w = e[j].w;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int main() {
    init();
    int u, v, w;
    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> w;
        add2(u, v, w);
    }
    dijkstra(1);
    cout << dis[n] << endl;
    return 0;
}

Dijkstra算法的核心思想是從未確定最短路的點(diǎn)的集合中選區(qū)一個最小的來更新其他的點(diǎn)，暴力枚舉的話時間復(fù)雜度是宅广，如果考慮堆優(yōu)化葫掉，用一個set來維護(hù)點(diǎn)的集合，復(fù)雜度可以降到
set的第二個參數(shù)代表堆的排序方法

typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N];  // 存儲單源最短路的結(jié)果
bool vst[MAX_N];  // 標(biāo)記每個頂點(diǎn)是否在集合 U 中
bool dijkstra(int s) {
    // 初始化 dist跟狱、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    min_heap.insert(make_pair(0, s));
    dist[s] = 0;
    for (int i = 0; i < n; ++i) {
        if (min_heap.size() == 0) {  // 如果小根堆中沒有可用頂點(diǎn)俭厚，說明有頂點(diǎn)無法從源點(diǎn)到達(dá)，算法結(jié)束
            return false;
        }
        // 獲取堆頂元素驶臊，并將堆頂元素從堆中刪除
        set<PII, less<PII> >::iterator iter = min_heap.begin();
        int v = iter->second;
        min_heap.erase(*iter);
        vst[v] = true;
        // 進(jìn)行和普通 dijkstra 算法類似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                // 先將對應(yīng)的 pair 從堆中刪除挪挤，再將更新后的 pair 插入堆
                min_heap.erase(make_pair(dist[x], x));
                dist[x] = dist[v] + e[j].w;
                min_heap.insert(make_pair(dist[x], x));
            }
        }
    }
    return true;  // 存儲單源最短路的結(jié)果
}

習(xí)題
1.騎車比賽

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int inf=0x3f3f3f;
int n,m;
int e[1001][1001];
int dis[1001];
bool vis[1001],have_e[1001][1001];
void dijkstra(int u){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[u]=0;
    for(int i=0;i<n;++i){
        int mind=inf,mint=-1;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&dis[j]<mind){
                mind=dis[j];
                mint=j;
            }
        }
        if(mint==-1)return;
        vis[mint]=true;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&have_e[mint][j]&&dis[j]>dis[mint]+e[mint][j]){
                dis[j]=dis[mint]+e[mint][j];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        e[u][v]=e[v][u]=w;
        have_e[u][v]=have_e[v][u]=true;
    }
    dijkstra(1);
    cout<<dis[n]<<endl;
    return 0;
}

SPFA單源最短路

SPFA單源最短路是bfs的隊列優(yōu)化版本
一般用di代表頂點(diǎn)到i的最短路，額外用一個隊列來保存即將進(jìn)行拓展的頂點(diǎn)列表用inqi來表示
算法步驟：
1.首先初始化关翎，初始隊列只包含源點(diǎn)扛门，且ds=0
2.取出隊列的頭頂點(diǎn)u，掃描從頂點(diǎn)u出發(fā)的每條邊纵寝，并進(jìn)行松弛操作论寨，若被松弛的頂點(diǎn)v不在隊列中，將v入隊
3.重復(fù)步驟2直到頂點(diǎn)為空
代碼：

bool inq[MAX_N];
int d[MAX_N];  // 如果到頂點(diǎn) i 的距離是 0x3f3f3f3f，則說明不存在源點(diǎn)到 i 的最短路
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (d[u] + e[i].w < d[v]) {
                d[v] = d[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

完整代碼：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct edge{
    int v,w,fail;
    edge(){}
    edge(int _v,int _w,int _fail){
        v=_v;
        w=_w;
        fail=_fail;
    }
}e[M<<1];
int head[N],len;
void init(){
    memset(head,-1,sizeof(head));
    len=0;
}
void add(int u,int v,int w){
    e[len]=edge(v,w,head[u]);
    head[u]=len++;
}
void add2(int u,int v,int w){
    add(u,v,w);
    add(v,u,w);
}

int n, m;
int dis[N];
bool vis[N];
void spfa(int u){
    memset(vis,false,sizeof(vis));
    vis[u]=true;
    memset(dis,0x3f,sizeof(dis));
    dis[u]=0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int j=head[u];~j;j=e[j].fail){
            int v=e[j].v;
            int w=e[j].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
}
int main() {
    init();
    int u,v,w;
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        add2(u,v,w);
    }
    spfa(1);
    cout<<dis[n]<<endl;
    return 0;
}

SPFA判斷負(fù)環(huán)
在進(jìn)行spfa時葬凳，用一個cnt數(shù)組記錄每個頂點(diǎn)的入隊次數(shù)绰垂，如果一個頂點(diǎn)入隊次數(shù)大于頂點(diǎn)總數(shù)n，則可以判斷存在負(fù)環(huán)火焰。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;

struct edge {
    int v, w, fail;
    edge() {}
    edge(int _v, int _w, int _fail) {
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M << 1];
int head[N], len;
void init() {
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
void add2(int u, int v, int w) {
    add(u, v, w);
    add(v, u, w);
}
int n, m;
int dis[N],in[N];
bool vis[N];
bool spfa(int u){
    memset(vis,false,sizeof(vis));
    vis[u]=true;
    memset(dis,0x3f,sizeof(dis));
    dis[u]=0;
    memset(in,0,sizeof in);
    in[u]=1;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int j=head[u];~j;j=e[j].fail){
            int v=e[j].v;
            int w=e[j].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                    ++in[v];
                    if(in[v]>n){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
int main() {
    init();
    int u, v, w;
    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> w;
        add2(u, v, w);
    }
    if(spfa(1)){
        cout<<"yes"<<endl;
    }else{
        cout<<"no"<<endl;
    }
    return 0;
}

Floyd多源最短路算法

是一種基于動態(tài)規(guī)劃的最短路算法
設(shè)是經(jīng)過1~k點(diǎn)的i到j(luò)的最短路劲装，對于k點(diǎn)，其可能經(jīng)過k點(diǎn)或者不經(jīng)過k點(diǎn)荐健。
狀態(tài)轉(zhuǎn)移方程：
代碼：

int g[N][N];  // 鄰接矩陣存圖
int dp[N][N][N];
void floyd(int n) {
    for (int k = 0; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (k == 0) {
                    dp[k][i][j] = g[i][j];
                } else {
                    dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
                }
            }
        }
    }    
}

但還可以把k這一維優(yōu)化掉酱畅，使dp數(shù)組退化為g數(shù)組，代碼：

int g[N][N];
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) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }    
}

完整代碼：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 101;
int g[N][N];
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){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}

int main() {
    memset(g,0x3f,sizeof(g));
    for(int i=0;i<N;++i){
        g[i][i]=0;
    }
    int n,m;
    int u,v,w;
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        g[u][v]=g[v][u]=w;
    }
    floyd(n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

次短路解法

次短路也分為兩種：1.可以經(jīng)過同一個點(diǎn) 2.不可經(jīng)過同一個點(diǎn)
第一種用dijkstra時江场，用兩個dis數(shù)組纺酸，一個記錄最短路，一個記錄次短路址否，每次更新時餐蔬，判斷是否更新最短路與次短路的值。
第二種則枚舉最短路的每條邊佑附，將其去掉樊诺，記錄剩下的最短路，取其最小的一個就是答案音同。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n,m;
struct node{
    int x,y;
}nodes[300];
struct edge{
    int v,fail;
    double w;
    edge(){}
    edge(int _v,double _w,int _fail){
        v=_v;
        w=_w;
        fail=_fail;
    }
}e[50000];
int head[50000],len;
void init(){
    memset(head,-1,sizeof(head));
    len=0;
}
void insert(int u,int v,double w){
    e[len]=edge(v,w,head[u]);
    head[u]=len++;
}
void insert2(int u,int v,double w){
    insert(u,v,w);
    insert(v,u,w);
}
double dis1[300],dis2[300];
bool vis1[300],vis2[300];
void dijkstra(int u){
    fill(dis1,dis1+n+1,1000100);
    fill(dis2,dis2+n+1,1000100);
    memset(vis1,false,sizeof(vis1));
    memset(vis2,false,sizeof(vis2));
    dis1[u]=0;
    for(int i=1;i<=2*n;++i){
        double mint=1000000;
        int v=-1,k;
        for(int j=1;j<=n;++j){
            if(!vis1[j]&&dis1[j]<mint){
                mint=dis1[j];
                k=1;
                v=j;
            }else if(!vis2[j]&&dis2[j]<mint){
                mint=dis2[j];
                k=2;
                v=j;
            }
        }
        if(v==-1)return;
        k==1?vis1[v]=true:vis2[v]=true;
        for(int j=head[v];~j;j=e[j].fail){
            int to=e[j].v;
            double w=e[j].w;
            if(dis1[to]>mint+w){
                dis2[to]=dis1[to];
                dis1[to]=mint+w;
            }else if(dis2[to]>mint+w)dis2[to]=mint+w;
        }
    }
}
int main(){
    init();
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=n;++i){
        cin>>x>>y;
        nodes[i]={x,y};
    }
    int u,v;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        double d=sqrt(pow(nodes[u].x-nodes[v].x,2)+pow(nodes[u].y-nodes[v].y,2));
        insert2(u,v,d);
    }
    dijkstra(1);
    printf("%.2lf\n",dis2[n]);
    return 0;
}

4.線段樹

一類問題可以抽象成n個數(shù)a1....an
1.查詢[l,r]中最小的數(shù)
2.修改ai為x
解決這類問題词爬，引入一個高級數(shù)據(jù)結(jié)構(gòu)：線段樹
用一棵二叉樹來表示線段樹，每個節(jié)點(diǎn)代表一個區(qū)間权均，每個非葉子結(jié)點(diǎn)都有左右兩個子樹顿膨，對每個結(jié)點(diǎn)，左結(jié)點(diǎn)編號2i叽赊，右結(jié)點(diǎn)編號2i+1恋沃，對于每一個結(jié)點(diǎn)如果其表示區(qū)間[l,r]。如果l=r必指，那么是一個葉子結(jié)點(diǎn)囊咏，否則令mid=(l+r)/2，左兒子為[l,mid]塔橡，右兒子為[mid+1,r]
線段樹的構(gòu)建是個遞歸的過程梅割，父節(jié)點(diǎn)的信息需要子節(jié)點(diǎn)去更新，所以需要遞歸的建立左右子樹葛家，代碼如下：

const int maxn = 10010;
int minv[4 * maxn], a[maxn];
// id 表示結(jié)點(diǎn)編號炮捧，l, r 表示左右區(qū)間
void build(int id, int l, int r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}

建樹的復(fù)雜度為O(n)，由于結(jié)點(diǎn)編號不一定連續(xù)惦银，所以minv數(shù)組大小一定要是節(jié)點(diǎn)數(shù)的四倍，這個經(jīng)過了嚴(yán)格的數(shù)學(xué)推導(dǎo)。id << 1 | 1代表2*id+1扯俱，但是一定不能用+而要用|书蚪，因為+的優(yōu)先級高于位運(yùn)算。遞歸的建立完左右子樹之后迅栅，我們需要用左右子樹的信息更新當(dāng)前節(jié)點(diǎn)殊校，這一步一般稱位pushup。
完整代碼：

#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn];
int minv[4*maxn];
void pushup(int id){
    minv[id]=min(minv[id<<1],minv[id<<1|1]);
}
void build(int id,int l,int r){
    if(l==r){
        minv[id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    build(1,1,n);
    return 0;
}

實現(xiàn)線段樹的單點(diǎn)更新

更新一次的復(fù)雜度為读存，因為數(shù)的深度為

// 把 x 位置更為成為 v
void update(int id, int l, int r, int x, int v) {
    if (l == r) {
        minv[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update(id << 1, l, mid, x, v);
    } else {
        update(id << 1 | 1, mid + 1, r, x, v);
    }
    pushup(id);
}

實現(xiàn)線段樹的單點(diǎn)查詢

單點(diǎn)查詢和單點(diǎn)更新很像为流，沿著鏈走到葉子結(jié)點(diǎn)就行了。

int query(int id, int l, int r, int x) {
    if (l == r) {
        return minv[id];
    }
    int mid = (l + r) >> 1;
    if (mid <= x) {
        return query(id << 1, l, mid, x);
    } else {
        return query(id << 1 | 1, mid + 1, r, x);
    }
}

區(qū)間查詢

對于查詢區(qū)間[x,y]就是將結(jié)點(diǎn)的區(qū)間合并起來让簿，每個子區(qū)間完全被查詢區(qū)間包含敬察，查詢區(qū)間的復(fù)雜度也是

int query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {  // 如果完全包含，直接返回
        return minv[id];
    }
    int mid = (l + r) >> 1;
    int ans = inf;
    if (x <= mid) {
        ans = min(ans, query(id << 1, l, mid, x, y));  // 如果左區(qū)間包含尔当，遞歸的查詢左子樹
    }
    if (y > mid) {
        ans = min(ans, query(id << 1 | 1, mid + 1, r, x, y));  // 如果右區(qū)間包含莲祸，遞歸的查詢右子樹
    }
    return ans;
}

完整代碼：

#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int a[maxn];
int minv[4 * maxn];
void pushup(int id) {
    minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
void build(int id, int l, int r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
void update(int id, int l, int r, int x, int v) {
    if (l == r) {
        minv[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update(id << 1, l, mid, x, v);
    } else {
        update(id << 1 | 1, mid + 1, r, x, v);
    }
    pushup(id);
}
int query(int id,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return minv[id];
    }
    int mid=(l+r)>>1;
    int ans=inf;
    if(x<=mid){
        ans=min(ans,query(id<<1,l,mid,x,y));
    }
    if(y>mid){
        ans=min(ans,query(id<<1|1,mid+1,r,x,y));
    }
    return ans;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int x, v;
        cin >> x >> v;
        update(1, 1, n, x, v);
    }
    int p;
    cin>>p;
    for(int i=0;i<p;++i){
        int l,r;
        cin>>l>>r;
        cout<<query(1,1,n,l,r)<<endl;
    }
    return 0;
}

斑點(diǎn)蛇

用于記錄區(qū)間和

#include <iostream>
#include <string>
using namespace std;
int N,a[50010],minv[200010];

void bulid(int id,int l,int r){
    if(l==r){
        minv[id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    bulid(id<<1,l,mid);
    bulid(id<<1|1,mid+1,r);
    minv[id]=minv[id<<1]+minv[id<<1|1];
}
void add(int id,int l,int r,int x,int v){
    if(l==r){
        minv[id]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)add(id<<1,l,mid,x,v);
    else add(id<<1|1,mid+1,r,x,v);
    minv[id]=minv[id<<1]+minv[id<<1|1];
}

void sub(int id,int l,int r,int x,int v){
    if(l==r){
        minv[id]-=v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)sub(id<<1,l,mid,x,v);
    else sub(id<<1|1,mid+1,r,x,v);
    minv[id]=minv[id<<1]+minv[id<<1|1];
}

int query(int id,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        return minv[id];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(x<=mid)ans+=query(id<<1,l,mid,x,y);
    if(y>mid)ans+=query(id<<1|1,mid+1,r,x,y);
    return ans;
}
int main(int argc, char** argv) {
    cin>>N;
    for(int i=1;i<=N;++i){
        cin>>a[i];
    }
    bulid(1,1,N);
    string input="";
    int a,b;
    while(1){
        cin>>input;
        if(input=="End")break;
        cin>>a>>b;
        if(input=="Add"){
            add(1,1,N,a,b);
        }else if(input=="Sub"){
            sub(1,1,N,a,b);
        }else if(input=="Query"){
            cout<<query(1,1,N,a,b)<<endl;
        }
    }
    return 0;
}

5.拓?fù)渑判?/h3>

拓?fù)渑判虮举|(zhì)上是一種bfs，代碼如下：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, next;
    int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}
int n,m;
int indegree[MAX_N];
void topo(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(indegree[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int now=q.front();
        cout<<now<<endl;
        q.pop();
        for(int i=p[now];i!=-1;i=E[i].next){
            int v=E[i].v;
            indegree[v]--;
            if(indegree[v]==0){
                q.push(v);
            }
        }
    }
}
int main() {
    init();
    memset(indegree,0,sizeof(indegree));
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        insert(u,v);
        indegree[v]++;
    }
    topo();
    return 0;
}

歐拉回路

若圖G中存在一條路徑使其恰好通過G中的每條邊一次椭迎，我們稱之為歐拉路徑（半歐拉圖）锐帜。若該路是一個環(huán)路，我們稱之為歐拉環(huán)路（歐拉圖）畜号。
判斷是否是歐拉圖缴阎，是否是歐拉回路
歐拉路徑的性質(zhì)，有且僅有兩個點(diǎn)的入度為奇數(shù)
歐拉圖的性質(zhì)简软，所有點(diǎn)的入度都為偶數(shù)

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, next;
    int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}
int n,m;
int degree[MAX_N];
int cnt;
bool vis[MAX_N];
void dfs(int u){
    vis[u]=true;
    cnt++;
    for(int i=p[u];i!=-1;i=E[i].next){
        int v=E[i].v;
        if(!vis[v]){
            dfs(v);
        }
    }
}

void euler(){
    dfs(1);
    if(cnt!=n){
        cout<<"It doesn't have an euler path!"<<endl;
        return;
    }
    int cntodd=0;
    for(int i=1;i<=n;i++){
        if(degree[i]%2==1){
            cntodd++;
        }
    }
    if(cntodd==0){
        cout<<"It has an euler circult"<<endl;
    }else if(cntodd==2){
        cout<<"It has an euler path!"<<endl;
    }else{
        cout<<"It doesn't have an euler path!"<<endl;
    }
}

int main() {
    init();
    memset(degree,0,sizeof(degree));
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        insert(u,v);
        insert(v,u);
        degree[u]++;
        degree[v]++;
    }
    euler();
    return 0;
}