| |
常用鏈接
留言簿
隨筆分類
隨筆檔案
文章分類
搜索
最新評論
閱讀排行榜
評論排行榜
Powered by: 博客園
模板提供：滬江博客
|
|
|
|
|
發新文章 |
|
 |
置頂隨筆
有朋友真好。
其實有時候只是想說說話，不是內心真的有疑問想尋求辦法，因為答案其實就在自己心中，自己心里明白得很......但人就是這樣，就算心里明白，也還是覺得憋，想找個人傾述。所以這時候，有朋友真好。朋友可以無償地陪你，聽你說話，跟你說話。
我今天其實也沒發生什么，只是想了一些東西，心情就變得不太愉快，但并不是不愉快，只是很想有個人罵一下自己！罵自己的不成熟，罵自己沒毅力，罵自己禁受不住挫折。然后我就找秦程聊天，聊著聊著，就釋懷了，就開朗了。
有朋友真好。我沒有好的文筆給解釋這句話。
我對親近的人都不輕易說謝謝，但今天我對秦程說了聲謝謝，因為今天打電話的時候我想到blue 跟我說的一句話：有朋友真好。
2013年5月31日
差分約束(difference constraints)，對，兩個關鍵字要理解好，“difference”簡單理解就是兩個節點的“差”，對應的就是圖中的邊權，而“約束”對應的是圖的邊。這個圖的邊權不一定都是正數，之前我一直很奇怪為什么做最短路的時候初始化dis[]為了0也可以，那是因為我沒意識到邊權可以為負數，而思維定勢地想初始化dis[]為0，那0不就是最小路徑了嗎，但這里差分約束的最短路徑常常是負數的，所以最短路徑可以不是0??！ 看網上講解的時候要小心，很多人把最長路和最短路是不分的，亂死了。 還有很重要的一點很多人沒區分開， 求最小可行解 ==> 把不等式劃為dv >= dx + Z的形式，即建立<u,v,Z>邊 ==> 可行解要最小，其實就是取約束條件中`最大`的約束 ==> 求最長路 解釋：為什么求最小可行解要劃成dv >= dx + Z形式？因為這個形式暗指了“讓dv盡量小”，因為此刻dv的取值區間為[du+Z, ∞]。 為什么可行解最小，即意味著取最大約束條件？這樣想，如果有dv >= du + Z1, dv >= du + Z2，(Z1<Z2)，那dv的最小取值就是du+Z2，因為du+Z1不滿足第二個約束條件。 最后一步就好理解了，因為建圖的邊權就是約束值，既然上一步指要取最大約束，那當然是求最長路啦。 網上很多講解沒有區分開所謂的最大/最小，一會兒指可行解的最，一會兒指約束條件的最，弄得我亂了好久。 順便貼一下： 求最大可行解 ==> 把不等式劃為dv <= dx + Z的形式，即建立<u,v,Z>邊 ==> 其實就是取約束條件中`最小`約束 ==> 求最短路 關于源點：很多時候額外價格源點可以幫我們把一個非連通圖變成連通圖，而對于源點的不等式，一定要和你之前建邊時的不等式形式一樣，如果之前是dv >= du + Z，那源點也要dv >= d0 + xxx。這個xxx就是dis[]的初始值，關于如何選取xxx，下面兩句話摘自百度百科： “ 1.如果將源點到各點的距離初始化為0，最終求出的最短路滿足 它們之間相互最接近了 2.如果將源點到各點的距離初始化為INF(無窮大)，其中之1為0，最終求出的最短路滿足 它們與該點之間相互差值最大。 ” 差分約束題目我一般是用SPFA+棧，為什么不用dijkstra+heap？因為dijkstra不能處理負環，而我們的題目可能有負環，所以干脆都用SPFA了，多數條件下，用stack的SPFA比用queue的快，why？因為常常地，用最先更新了的點去更新其它點，效果比用以前已經更新了的點(在queue的tail)好。 差分約束專題：http://972169909-qq-com.iteye.com/blog/1185527 poj 1201 差分約束 題意：求符合題意的最小集合Z的元素個數，約束條件:i j C，表區間[i,j]至少有C個Z集合的元素。 隱含條件是，S區間是個連續的數字區間，0 <= s[i+1] - s[i] <= 1，其中s[i]表0~i中有多少數字是Z集合元素。下面是隱含條件的建邊。 for(int i = 0; i < 50001; i++) { //@ vert[i].push_back(i+1); edge[i].push_back(0); vert[i+1].push_back(i); edge[i+1].push_back(-1); } poj 1364 差分約束 題意：約束條件：i, n, op, K --> op分greater和less，需要滿足Si + S[i+1] + S[i+2] + ... + S[i+n] > K （或小于） 因為我是用dis[i]表示S0+S1+...+Si的和，所以<u,v,w>應該表示的意思是sum[v]-sum[u-1] = w，所以這里0也是一個點，所以源點不能取0！ //@ ?? 我在SPFA后面輸出了dis[]數組來看，這些值并不符合題目的要求，那為什么整個程序是對的？如果要輸出一個解的話怎么寫？ 答：因為這里的dis[i]表示的是s1+s2+...+si的和，用第一個樣例來說， sample input: 4 2 1 2 gt 0 2 2 lt 2 輸出的dis[0--n] : -1 0 0 0 0 s1+s2+s3 = sum[3] - sum[1-1] = dis[3] - dis[0] = 1 , 滿足gt 0 s2+s3+s4 = sum[4] - sum[2-1] = dis[4] - dis[1] = 0 , 滿足lt 2 所以，{si}的一組解應該為0,1,0,0,0. poj 1983 差分約束 題意：給出兩種約束條件，一種是P A B X，意為精確地約束A比B遠X個單位；另一種V A B，意為模糊地約束A至少比B遠1個單位。是否有可行解？ 好點：兩種約束條件，其中Precise約束可以轉換為X <= A-B <= X 有V i i 這種數據，這種數據在SPFA里會WA，在ballman_ford里AC，不過預處理一下就可以了，還是用SPFA. hdu 3666 差分約束 題意：給出矩陣{Cij}，問是否存在數列{A} 和 {B}，使得對于矩陣內所有Xij滿足: L <= Xij * Ai / Bj <= U 構圖。用log把乘除變成加減，就可以差分約束來做了。我用的是SPFA+stack求最短路，最長路應該也是可以的。沒有建源點，直接一開>始把所有點push進去... 14xx ms 過挺險的~
2013年5月28日
做第一道查分約束poj 3159...TLE不斷。估計管理員是跟C++的STL過不去，就卡用vector的人了。。而我已經好久好久沒人工寫什么鄰接表，前向星什么的了，就只能TLE過不了了。。換了什么dijkstra+優先隊列，SPFA+stack優化，只要用vector來存邊，估計都過不了。 下面是TLE代碼，留紀念。 #include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int n, m;
int dis[30001];
bool visit[30001];
int S[30001], S_top = 0;
vector<int> vert[30001], edge[30001];
void dijkstra(int s);
int main()
{
int u,v,w;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
vert[u].push_back(v);
edge[u].push_back(w);
}
dijkstra(1); //最長路-----不是的，是最短路！
printf("%d\n", dis[n]);
}
void dijkstra(int s)
{
memset(dis, 127, sizeof(dis));
dis[s] = 0;
visit[s] = true;
S[++S_top] = s;
while(S_top > 0) {
int u = S[S_top--];
visit[u] = false;
for(int Size = vert[u].size(), i = 0; i < Size; i++) {
int v = vert[u][i];
if(dis[v] > dis[u] + edge[u][i]) {
dis[v] = dis[u] + edge[u][i];
if(visit[v] == false) {
S[++S_top] = v;
visit[v] = true;
}
}
}
}
}
2013年5月27日
/* 最短路 好題 題意：給出邊建圖，然后分別刪除各條邊，問每一次刪邊后的所有端點的兩兩最短路之和，若有一對端點不連通，則返回INF 思路：暴力解法是每次刪邊后都來n次最短路。這里面的冗余就是刪除的邊并不影響一些點的最短路樹，所以這些點可以不用在刪邊后都來次dijkstra>。標程解法就是在暴力解法上加上一些剪枝。先預處理出所有點的最短路樹，記x的最短路樹的和為sum[x]?，F在來去掉冗余：在預處理時用used[x][u][v]記錄點x的最短路樹是否用到了邊u--v，則刪除邊u--v的時候，判斷點x的最短路樹是否用到邊u--v的，若用到，則對x做一次dijkstra，用新的sum[x]表示>當前最短路樹；否則用預處理的sum[x]就可以，不用再dijkstra. dijkstra是利用`邊權為1`這一特性來加快的版本，具體看:http://www.shnenglu.com/keroro/archive/2013/05/27/200621.html 這道題有很多重邊，這估計也是考點之一，不好好處理重邊的話會超時。 多數題解是錯的，因為hdu上的這道題的數據比較水才可以過，可以試試discuss里給的數據，下面這幾個題解比較靠譜。 http://blog.csdn.net/nash142857/article/details/8253913 http://www.cnblogs.com/crisxyj/archive/2013/03/10/2952396.html http://hi.baidu.com/novosbirsk/item/bfcf0cd201edfc2d39f6f709 兩份代碼的思想是完全一樣的，只是“baidu blog”那份用w[i][e]來判斷i的最短路樹是否包括邊e，而cnblog的那份是用used[x][u][v]來判斷邊u-->v是否xxx. */ #include <algorithm> #include <stdio.h> #include < string.h> #include <vector> #include <deque> using namespace std; #define MAXN 101 #define INF 99999999 #define debug printf("!\n") struct Edge { int u,v; } edge[3001]; vector< int> vertex[MAXN]; int visit[MAXN], sum[MAXN], cnt[MAXN][MAXN]; //cnt[u][v]表u--v的邊有多少條，用來處理重邊
bool used[MAXN][MAXN][MAXN]; //used[x][u][v]x的最短路樹是否用到了邊u--v
int n, m; void init(); void dijkstra( int s, int when, int flag); int main() { int when = 0; int u, v; while(scanf("%d%d", &n, &m) != EOF) { init(); for( int i = 0; i < m; i++) { scanf("%d%d", &u, &v); vertex[u].push_back(v); vertex[v].push_back(u); edge[i].u = u, edge[i].v = v; cnt[u][v]++, cnt[v][u]++; } int ans = 0; for( int i = 1; i <= n; i++) { dijkstra(i, ++when, 1); ans += sum[i]; } for( int i = 0; i < m; i++) { int tmp = ans; int u = edge[i].u, v = edge[i].v; //forbid_u = edge[i].u, forbid_v = edge[i].v; 因為有重邊所以不能用這種方法
for( int j = 1; j <= n; j++) if(used[j][u][v] && cnt[u][v] == 1) { //不加cnt[u][v] == 1會超時。?？ǖ木褪侵剡?，靠！
int tmp = sum[j]; sum[j] = 0; //vector<int> :: iterator it1 = find(vertex[u].begin(), vertex[u].end(), v);
//vector<int> :: iterator it2 = find(vertex[v].begin(), vertex[v].end(), u);
//*it1 = u, *it2 = v;
cnt[u][v]--, cnt[v][u]--; dijkstra(j, ++when, 2); cnt[u][v]++, cnt[v][u]++; //*it1 = v, *it2 = u; //本來是用erase的，超時了。 現在換這種方法也超時了，估計find耗時太久。
ans = ans - tmp + sum[j]; //用新的sum[j]來代替舊的tmp
sum[j] = tmp; int k ; for(k = 1; k <= n; k++) if(visit[k] != when) break; //如果刪邊了以后j不能到達k(即k沒有進過隊)
if(k <= n) { ans = INF; break; } } ans == INF ? printf("INF\n") : printf("%d\n", ans); ans = tmp; //不要把這個tmp和for_j里的tmp混了..
} for( int i = 0; i < m; i++) cnt[edge[i].u][edge[i].v] = cnt[edge[i].v][edge[i].u] = 0; //初始化 因為感覺memset(cnt)會不會花更多時間
} return 0; } void dijkstra( int s, int when, int flag) { int floors = 1; int cur = 0; deque< int> Q[2]; Q[cur].push_back(s); visit[s] = when; do { while(!Q[cur].empty()) { int u = Q[cur].front(); Q[cur].pop_front(); for( int Size = vertex[u].size(), i = 0; i < Size; i++) { int v = vertex[u][i]; if(visit[v] != when && cnt[u][v] > 0) { if(flag == 1) used[s][u][v] = used[s][v][u] = true; //第一次最短路才標記used因為懶得寫兩遍，所以要flag來標記是刪邊前還收刪邊后做的最短路，1則是預處理時的最短路，此時要標記used；2則是刪邊后的最短路，這個時候不能標記used.
visit[v] = when; sum[s] += floors; Q[1-cur].push_back(v); } } } floors++; cur = 1 - cur; } while(!Q[cur].empty()); } void init() { memset(sum, 0, sizeof(sum)); memset(used, false, sizeof(used)); for( int i = 1; i <= n; i++) vertex[i].clear(); }
/* 最短路, 終點集合到s的最遠距離最短，求s. 即已知終點集hvzpftn求一s使得Min{ max{ dis(s, di) } } 好題 思路： 多次單源最短路，選出最大值 在對每個x進行分層搜索的過程中, 用max_d[y]記錄每個地區x到達地區y的最短距離中的最大值. 最后求得的Star Value就是max_d[]中的最小值. 由于題目的特殊性`邊權都為1`，所以可以借助這一性質變換一下SPFA使其更快。 說個題外話，在臨高時看到有個學弟拓撲排序用到“分層思想”，一直覺得很妙。就是拓撲后我們可以得到floor[i]，如果floor[i] > floor[j]，即說明j是i的前驅節點（層數越小越接近root）; 而floor[i] == floor[j]的話則i，j的相對順序無所謂，因為他們都在“同一層”。 這里因為邊權都為1，所以SPFA可以用到上述的分層思想，層數越高，離source越遠。代碼里面floors就表示層數，Q是滾動隊列，就是一層一層地relax后繼節點。 注意?。∏f不要以為max_d[]是最短路算法里面的dis[]，這里的max_d[i]是到點i到終點集合{di}的最大值！而常規最短路算法里的dis[]已經被省略為“層數”了，不需要記錄，所以沒開數組。 最重要的是學到一個tip??！以前我做多次最短路的時候總要每次都初始化visit[] -> false，但其實不用的，我們只要用一個變量when表示“這是第幾次做SPFA(或其他)“，然后每次入隊前都看”是否當前visit[v] == when就可以直到改點是否已經入過隊...... */ #include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
using namespace std;
#define debug printf("!\n")
#define INF 999999999
#define MAXN 10000
int n;
int max_d[MAXN];
int visit[MAXN];
vector<int> v[MAXN];
void SPFA(int s, int when);
void init();
int main()
{
int cases, query, id, m, y, x;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &query);
init();
for(int i = 0; i < n; i++) {
scanf("%d%d", &id, &m);
while(m--) {
scanf("%d", &y);
v[id].push_back(y);
}
}
int when = 0;
while(query--) {
scanf("%d", &m);
while(m--) {
scanf("%d", &x);
SPFA(x, ++when);
}
}
int ans = INF, ans_id = -1;
for(int i = 1; i < MAXN; i++) if(!v[i].empty() && max_d[i] < ans) ans = max_d[i], ans_id = i;
printf("%d %d\n", ans, ans_id);
}
return 0;
}
void init()
{
for(int i = 0; i < MAXN; i++) v[i].clear();
memset(max_d, 0, sizeof(max_d));
memset(visit, 0, sizeof(visit));
}
void SPFA(int s, int when)
{
deque<int> Q[2];
int cur = 0;
Q[cur].push_back(s);
max_d[s] = max(max_d[s], 1);
visit[s] = when;
int floors = 1;
do {
floors++;
while(!Q[cur].empty()) {
int at = Q[cur].front();
Q[cur].pop_front();
for(int Size = v[at].size(), i = 0; i < Size; i++) {
int to = v[at][i];
if(visit[to] != when) { //是否已入隊
//max_d[to] = max(max_d[to], max_d[at]+1); 這句是不對的，因為這個分層跟拓撲排序的分層是不一樣的，拓撲排序是要在入度為0時才能加進隊Q，所以可以這樣寫，但是這里只要第一次遇見點to就必須得入隊，因為要的是最短路徑
max_d[to] = max(max_d[to], floors); //不把這句放在if外面，因為這里的max_d[to]是距離s的最短路徑，最短路徑也就是最小層數，最小層數在to第一次入隊的時候已經得到了
visit[to] = when;
Q[1-cur].push_back(to);
}
}
}
cur = 1 - cur;
} while(!Q[cur].empty());
}
2013年5月17日
/*
最小公共祖先
題意: 給出一顆無向有邊權樹, 詢問若干個(u,v)對的距離.
所謂LCA 的Tarjan算法, 實際上就是在建樹的過程中把query中的lca給計算出來, 所以稱為`離線算法` . 是的, 本質就是這么簡單, 好多解釋都搞復雜了.
步驟略, 自己google.
理解這個算法一定要抓住`遞推`的思想(也有遞歸在里面, 也要抓住).
Tarjan是利用并查集實現的, 在遞推過程中, 一棵樹的root節點代表這棵樹(聯系并查集來想), 這樣做的好處是, 如果問點i與j的lca, 我們只要找i,j都屬于的最小的哪棵子樹就行了, 因為該子樹就是我們的答案. 那如何確定是那顆子樹呢? 這一點后面再解釋一下.
下面說Tarjan最巧妙的點了. 因為是在建樹的過程中計算所有query, 也就表示我們此刻是否能計算某一query對(u,v)的條件是 : u和v是否都已經遍歷過. 所以我們可以在遍歷到點v(假設經歷v的時間比u晚)的時候把query給計算出來. 比如lcm(u,v)就是find(u). 那此刻的find(v)和lcm(u,v)相不相等呢? 答案是不相等, 至少在我的代碼實現上不相等. 因為father[x]的更新是在`遞歸回去`的時候更新的, 而此刻在遍歷v點, 還沒遞歸回去呢, father[v]當然也就沒更新啦.
其實上一段就已經回答了`如何確定哪棵子樹是我們想要的答案`這一問題了. 就是find(u)所代表的子樹! 注意, 是find(u), 不是find(v)! 因為u是在v之前已經被遍歷過了, 并且遞歸回去過sub_root過了, 也就是father[u]被更新為sub_root了, 所以find(u)可以代表當前的sub_tree, 即`最小包含(u,v)子樹`
下面兩個解釋, 推薦一下. 羅嗦一句, 看代碼更容易理解, 人腦模擬一遍更容易理解
http://www.nocow.cn/index.php/Tarjan%E7%AE%97%E6%B3%95
http://blog.chinaunix.net/uid-1721137-id-181005.html
*/
#include <vector>
#include <stdio.h>
using namespace std;
#define MAXN 40001
#define debug printf("!\n")
vector<int> v[MAXN], w[MAXN], query[MAXN], ans_num[MAXN];
int father[MAXN], dis[MAXN], ans[201];
bool visit[MAXN];
int n;
void init()
{
for(int i = 1; i <= n; i++) {
v[i].clear();
w[i].clear();
ans_num[i].clear();
query[i].clear();
father[i] = i;
dis[i] = 0;
visit[i] = false;
}
}
int find(int x)
{
return x == father[x] ? x : father[x] = find(father[x]);
}
void Union(int x, int y) { father[find(y)] = find(x); }
void Tarjan(int now, int value)
{
visit[now] = true;
dis[now] = value;
for(int Size = v[now].size(), i = 0; i < Size; i++) {
int tmp = v[now][i];
if(visit[tmp] != 0) continue;
Tarjan(tmp, value + w[now][i]);
Union(now, tmp); //注意順序, 先Tarjan子節點tmp, 再更新其father[tmp], 因為要保證在遞推tmp所代表的子樹時, father[tmp] = tmp, 而與當前子樹無關. 遞歸回來的時候再把tmp代表的子樹`并入`到當前樹里
}
for(int Size = query[now].size(), i = 0; i < Size; i++) {
int tmp = query[now][i];
if(!visit[tmp]) continue; //若visit[tmp] == true, 即表示tmp節點已經遍歷過, 此時可計算相應的query
ans[ans_num[now][i]] = dis[now] + dis[tmp] - 2 * dis[find(tmp)];
}
}
int main()
{
int cases, Query, x, y, z;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &Query);
init();
for(int i = 1; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
v[x].push_back(y);
w[x].push_back(z);
v[y].push_back(x);
w[y].push_back(z);
}
for(int i = 0; i < Query; i++) {
scanf("%d%d", &x, &y);
query[x].push_back(y);
query[y].push_back(x);
ans_num[x].push_back(i);
ans_num[y].push_back(i);
}
Tarjan(1, 0);
for(int i = 0; i < Query; i++) printf("%d\n", ans[i]);
}
return 0;
}
2013年4月4日
在coursera上上看了兩周的Scala, 剛才奇怪為什么Scala對于一般函數嚴格要求指明參數類型的語言, 對于匿名函數卻可以不用指明參數類型?
google無果. 不想查了. 習慣了Scheme/SML這樣有類型推導系統的語言, 再來寫Scala有點排斥心理, 而且Scala更過分的是要連函數的返回類型也要寫...喂喂, 這都完全喪失了FP的美感了吧 >_<
突然想起來, 昨天才發現SML內置沒有對大數的操作---好失望~
當初選這門課是好奇它能把面向對象與函數式能結合到多大程度, 現在看來沒什么令人驚奇的, 不貶不贊. 還是原生函數式語言比較好玩.
如果你是被標題騙過來的, 能回答標題的問題就請給我講講吧~謝謝!
2012年6月10日
2012年3月17日
有朋友真好。
其實有時候只是想說說話，不是內心真的有疑問想尋求辦法，因為答案其實就在自己心中，自己心里明白得很......但人就是這樣，就算心里明白，也還是覺得憋，想找個人傾述。所以這時候，有朋友真好。朋友可以無償地陪你，聽你說話，跟你說話。
我今天其實也沒發生什么，只是想了一些東西，心情就變得不太愉快，但并不是不愉快，只是很想有個人罵一下自己！罵自己的不成熟，罵自己沒毅力，罵自己禁受不住挫折。然后我就找秦程聊天，聊著聊著，就釋懷了，就開朗了。
有朋友真好。我沒有好的文筆給解釋這句話。
我對親近的人都不輕易說謝謝，但今天我對秦程說了聲謝謝，因為今天打電話的時候我想到blue 跟我說的一句話：有朋友真好。
2011年10月30日
|
|