聞?wù)f還能用在負(fù)權(quán),和有環(huán)圖...繼續(xù)研究
const
?
int
?MAXN?
=
?
101
;
const
?
int
?INF?
=
?
1000000
;
int
?g[MAXN][MAXN];
int
?d[MAXN][MAXN];
int
?floyd(
int
?n)
{
????
int
??i,?j,?k;
????
for
?(i
=
1
;?i
<=
n;?i
++
)
????????
for
?(j
=
1
;?j
<=
n;?j
++
)
????????????d[i][j]?
=
?g[i][j];
????
for
?(k
=
1
;?k
<=
n;?k
++
)
????
{
????????
for
?(i
=
1
;?i
<=
n;?i
++
)
????????????
for
?(j
=
1
;?j
<=
n;?j
++
)
????????????
{
????????????????
if
?(d[i][k]?
<
?INF?
&&
?d[k][j]?
<
?INF
????????????????
&&
?d[i][k]?
+
?d[k][j]?
<
?d[i][j])
????????????????????d[i][j]?
=
?d[i][k]?
+
?d[k][j];
????????????}
????}
????
return
?
0
;
}
//------------------------------
給我一年時(shí)間,? 把你們都搞
定, 呵呵, 做個(gè)好夢(mèng)先!~
------------------------------//
圖論?
???????路徑問(wèn)題?
??????????????最短路徑?
?????????????????????0/1?邊權(quán)最短路徑?
BFS?
?
?????????????????????非負(fù)邊權(quán)最短路徑?
Dijkstra?
u???????可以用Dijkstra解決的問(wèn)題的特征?
?
?????????????????????負(fù)邊權(quán)最短路徑?
Bellman-Ford?
u???????Bellman-Ford的Yen-氏優(yōu)化?
u???????差分約束系統(tǒng)?
?
????????????????????????????Floyd?
u???????廣義路徑問(wèn)題?
u???????傳遞閉包?
u???????極小極大距離?/?極大極小距離?
?
Euler?Path?/?Tour?
???????圈套圈算法?
???????混合圖的?Euler?Path?/?Tour?
?
Hamilton?Path?/?Tour?
???????特殊圖的Hamilton?Path?/?Tour?構(gòu)造?
?
生成樹(shù)問(wèn)題?
??????????????最小生成樹(shù)?
?????????????????????第k小生成樹(shù)?
?
??????????????最優(yōu)比率生成樹(shù)?
u???????0/1分?jǐn)?shù)規(guī)劃?
?
??????????????度限制生成樹(shù)?
?
???????連通性問(wèn)題?
u???????強(qiáng)大的DFS算法?
?
??????????????無(wú)向圖連通性?
?????????????????????割點(diǎn)?
割邊?
二連通分支?
?
??????????????有向圖連通性?
?????????????????????強(qiáng)連通分支?
u???????2-SAT?
u???????最小點(diǎn)基?
?
有向無(wú)環(huán)圖?
???????拓?fù)渑判?
u???????有向無(wú)環(huán)圖與動(dòng)態(tài)規(guī)劃的關(guān)系?
?
二分圖匹配問(wèn)題?
u???????一般圖問(wèn)題與二分圖問(wèn)題的轉(zhuǎn)換思路?
?
最大匹配?
u???????有向圖的最小路徑覆蓋?
u???????0?/?1矩陣的最小覆蓋?
?
???????完備匹配?
?
???????最優(yōu)匹配?
?
網(wǎng)絡(luò)流問(wèn)題?
u???????網(wǎng)絡(luò)流模型的簡(jiǎn)單特征和與線(xiàn)性規(guī)劃的關(guān)系?
?
???????最大流最小割定理?
?
???????最大流問(wèn)題?
有上下界的最大流問(wèn)題?
u???????循環(huán)流?
?
最小費(fèi)用最大流?/?最大費(fèi)用最大流?
?
弦圖的性質(zhì)和判定?
?
組合數(shù)學(xué)?
u???????解決組合數(shù)學(xué)問(wèn)題時(shí)常用的思想?
u???????逼近?
u???????遞推?/?動(dòng)態(tài)規(guī)劃?
?
???????概率問(wèn)題?
?
???????Polya?定理?
???????
?
計(jì)算幾何?/?解析幾何?
u???????計(jì)算幾何的核心：叉積?/?面積?
u???????解析幾何的主力：復(fù)數(shù)?
?
基本形?
???????點(diǎn)?
???????直線(xiàn)，線(xiàn)段?
???????多邊形?
凸多邊形?/?凸包?
u???????凸包算法的引進(jìn)，卷包裹法?
???????Graham?掃描法?
u???????水平序的引進(jìn)，共線(xiàn)凸包的補(bǔ)丁?
完美凸包算法?
?
???????相關(guān)判定?
??????????????兩直線(xiàn)相交?
??????????????兩線(xiàn)段相交?
??????????????點(diǎn)在任意多邊形內(nèi)的判定?
??????????????點(diǎn)在凸多邊形內(nèi)的判定?
???????
???????經(jīng)典問(wèn)題?
??????????????最小外接圓?
?????????????????????近似O(n)的最小外接圓算法?
?
??????????????點(diǎn)集直徑?
?????????????????????旋轉(zhuǎn)卡殼，對(duì)踵點(diǎn)?
???????
???????多邊形的三角剖分?
?
數(shù)學(xué)?/?數(shù)論?
???????最大公約數(shù)?
??????????????Euclid?算法?
?????????????????????擴(kuò)展的Euclid算法?
????????????????????????????同余方程?/?二元一次不定方程?
????????????????????????????同余方程組?
?
???????線(xiàn)性方程組?
??????????????高斯消元法?
u???????解mod?2域上的線(xiàn)性方程組?
u???????整系數(shù)方程組的精確解法?
?
矩陣?
???????行列式的計(jì)算?
u???????利用矩陣乘法快速計(jì)算遞推關(guān)系?
?
???????分?jǐn)?shù)?
??????????????分?jǐn)?shù)樹(shù)?
??????????????連分?jǐn)?shù)逼近?
?
???????數(shù)論計(jì)算?
??????????????求N的約數(shù)個(gè)數(shù)?
??????????????求phi(N)?
??????????????求約數(shù)和?
??????????????……?
???????
???????素?cái)?shù)問(wèn)題?
??????????????概率判素算法?
??????????????概率因子分解?
?
數(shù)據(jù)結(jié)構(gòu)：?
???????組織結(jié)構(gòu)?
??????????????二叉堆?
?????????????????????左偏樹(shù)?
??????????????勝者樹(shù)?
??????????????Treap?
?
統(tǒng)計(jì)結(jié)構(gòu)?
樹(shù)狀數(shù)組?
虛二叉樹(shù)?
線(xiàn)段樹(shù)?
u???????矩形面積并?
u???????圓形面積并?
?
???????關(guān)系結(jié)構(gòu)?
??????????????Hash?表?
并查集?
u???????路徑壓縮思想的應(yīng)用?
?
???????STL?中的數(shù)據(jù)結(jié)構(gòu)?
??????????????vector?
??????????????deque?
set?/?map?
??????????????
動(dòng)態(tài)規(guī)劃?/?記憶化搜索?
u???????動(dòng)態(tài)規(guī)劃和記憶化搜索在思考方式上的區(qū)別?
?
???????最長(zhǎng)子序列系列問(wèn)題?
??????????????最長(zhǎng)不下降子序列?
?
???????最長(zhǎng)公共子序列?
?
???????一類(lèi)NP問(wèn)題的動(dòng)態(tài)規(guī)劃解法?
?
???????樹(shù)型動(dòng)態(tài)規(guī)劃?
?
???????背包問(wèn)題?
?
???????動(dòng)態(tài)規(guī)劃的優(yōu)化?
u???????四邊形不等式?
u???????狀態(tài)設(shè)計(jì)?
u???????規(guī)劃方向（？）?
???????
常用思想?
???????二分?
?
???????最小表示法?
#include?
<
iostream
>
using
?
namespace
?std;
const
?
int
?MAXN?
=
?
100
;
class
?UFset
{
public
:
????
int
?parent[MAXN];
????UFset();
????
int
?Find(
int
);
????
void
?Union(
int
,?
int
);
}
;
UFset::UFset()
{
????memset(parent,?
-
1
,?
sizeof
(parent));
}
int
?UFset::Find(
int
?x)
{
????
if
?(parent[x]?
<
?
0
)
????????
return
?x;
????
else
????
{
????????parent[x]?
=
?Find(parent[x]);
????????
return
?parent[x];
????}
//
?壓縮路徑
}
void
?UFset::Union(
int
?x,?
int
?y)
{
????
int
?pX?
=
?Find(x);
????
int
?pY?
=
?Find(y);
????
int
?tmp;
????
if
?(pX?
!=
?pY)
????
{
????????tmp?
=
?parent[pX]?
+
?parent[pY];?
//
?加權(quán)合并
????????
if
?(parent[pX]?
>
?parent[pY])
????????
{
????????????parent[pX]?
=
?pY;
????????????parent[pY]?
=
?tmp;
????????}
????????
else
????????
{
????????????parent[pY]?
=
?pX;
????????????parent[pX]?
=
?tmp;
????????}
????}
}
int
?main()
{
????
return
?
0
;
}
有bug請(qǐng)指正:)
先是晚上睡不著， 一直在想那道DP題， 倒是讓我AC掉了， 算是安慰。
然后下午pku e10, 看到別人都7題6題那樣， 而我還是一題都做不出來(lái)， 那種情景， 真是... 最終只能做出《算法藝術(shù)》上講過(guò)的那道加括號(hào)的DP,? 再而確定了，書(shū)上的代碼是錯(cuò)的， 那時(shí)候，在真的是不知道應(yīng)該開(kāi)心， 還是不開(kāi)心好了。
到了晚上，我寫(xiě)了一個(gè)小時(shí)得6K的高精度， 結(jié)果換來(lái)了TLE，?真是欲哭無(wú)淚。?
就是這樣， 又做了一天的題目， 每天都是這樣做了， 什么時(shí)候能看看書(shū)呢？ 嗯， 就明天， 看Floyd和DP!
放假回去了一個(gè)星期，見(jiàn)一下apple, 爸爸媽媽?zhuān)贤瑢W(xué)，又跑回學(xué)校了。
沒(méi)辦法，現(xiàn)在連DP都寫(xiě)不出來(lái)的我， 再不花時(shí)間努力， 老師要求的400題是完成不了的。還好， 宿舍還有我的戰(zhàn)友們， 所以也不會(huì)覺(jué)得寂寞， 至少還可以一起喝糖水啊^_^！
回來(lái)這兩個(gè)星期， 都泡在了acm的題目上面， 本來(lái)說(shuō)要學(xué)點(diǎn)英語(yǔ)的（還好期末英語(yǔ)沒(méi)掛）， 但是也無(wú)暇兼顧了， 可是我還是覺(jué)得進(jìn)度有點(diǎn)慢， 或者我自己又開(kāi)始浮躁了， 對(duì)于acm， 接觸了半年了， 雖然參加了校賽和省賽， 拿了點(diǎn)小獎(jiǎng)， 但是對(duì)比起那些有OI基礎(chǔ)的牛牛和那些數(shù)學(xué)特強(qiáng)的牛牛門(mén)（比如一個(gè)月可以330題的ghost_wei）， 我真的是菜到不能再菜了， 最郁悶的是， 到現(xiàn)在連DP都寫(xiě)不出來(lái)， 我到底什么時(shí)候才能達(dá)到一看到題目， 就能構(gòu)造出DP狀態(tài)的境界呢?
嗯， 要繼續(xù)努力了，不能浮躁， 加油， 爭(zhēng)取這個(gè)月把DP搞定！