生活随笔
收集整理的這篇文章主要介紹了
图论复习汇总
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
三元環計數&四元環計數
Blog
dfs樹,點雙,邊雙,強連通分量
Blog
bfs樹
對一個圖運行 bfs 算法，每個點uuu的父親定義為第一次遍歷uuu時的前驅結點，若無則為根。
非樹邊只存在在同一層的兩個點和相鄰層的點中。
hihoCoder1147 時空陣
題意：
問111號點到nnn號點距離恰好為mmm的圖的個數。圖的邊權為111。
n,m≤100n,m \leq 100n,m≤100
題解：
dp(i,j,k)dp(i,j,k)dp(i,j,k) 表示做了前iii層，上一層用jjj個點，共用kkk個點的方案數。
轉移枚舉這一層的連邊方式，做到mmm層即可。
對于mmm層之后的邊可以隨便亂連。
一個小問題如何保證nnn在第 m 層，只要對答案×jn?1\times \frac{j}{n-1}×n?1j?即可。
#include<iostream>
#include<cstdio>
using namespace std
;
typedef long long ll
;
const int mod
=1e9+7;
int pw
[10005],C
[105][105];
int n
,L
;
ll f
[105][105][105],ans
;
ll
power(ll a
,int b
){ll ans
=1;while(b
){if(b
&1) ans
=ans
*a
%mod
;a
=a
*a
%mod
;b
>>=1; }return ans
;
}
int main(){scanf("%d%d",&n
,&L
);pw
[0]=1;for(int i
=1;i
<=n
*n
;i
++) pw
[i
]=pw
[i
-1]*2%mod
;for(int i
=0;i
<=n
;i
++)C
[0][i
]=0,C
[i
][0]=1; for(int i
=1;i
<=n
;i
++)for(int j
=1;j
<=i
;j
++)C
[i
][j
]=(C
[i
-1][j
]+C
[i
-1][j
-1])%mod
;f
[0][1][1]=1;for(int i
=1;i
<=L
;i
++){for(int j
=i
+1;j
<=n
-L
+i
;j
++){for(int k
=1;k
<=j
-i
;k
++){for(int x
=1;x
<=j
-k
-i
+1;x
++){if(i
<L
)f
[i
][j
][k
]=(f
[i
][j
][k
]+f
[i
-1][j
-k
][x
]*power(pw
[x
]-1,k
)%mod
*pw
[C
[k
][2]]%mod
*C
[n
-j
+k
-1][k
]%mod
)%mod
;else if(i
==L
)f
[i
][j
][k
]=(f
[i
][j
][k
]+f
[i
-1][j
-k
][x
]*power(pw
[x
]-1,k
)%mod
*pw
[C
[k
][2]]%mod
*C
[n
-j
+k
-1][k
-1]%mod
)%mod
;}}}}for(int j
=1;j
<=n
;j
++){for(int k
=1;k
<=j
;k
++){ans
=(ans
+f
[L
][j
][k
]*pw
[k
*(n
-j
)]%mod
*pw
[C
[n
-j
][2]]%mod
)%mod
;}}printf("%lld\n",ans
);return 0;
}
[XSY3512] 標記的連接圖
最短路
Blog
差分約束系統
- 若求最長路：
對于u→vu\to vu→v，有dis[v]≥dis[u]+wdis[v]\geq dis[u]+wdis[v]≥dis[u]+w
若圖中存在正環，無解 - 若求最短路：
對于u→vu\to vu→v，有dis[v]≤dis[u]+wdis[v]\leq dis[u]+wdis[v]≤dis[u]+w
若圖中存在負環，無解
[POI2015] Pustynia
并查集
Blog
最小生成樹 MST
Blog
拓撲排序
Blog
歐拉回路&哈密頓回路
Blog
二分圖匹配
Blog
網絡流
Blog
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的图论复习汇总的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
