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