oyjpArt ACM/ICPC算法程序設(shè)計空間

下面我用n代表點 m代表邊
鄰接表：訪問任任兩點之間的邊最壞o(n) 遍歷一個點的所有邊o(該點的度數(shù)）
鄰接矩陣：訪問任兩點之間的邊o(1) 但是遍歷一個點的所有邊o(n)
由此可以看出 選擇是有目的的
第一 對于稀疏圖 有時候內(nèi)存不夠用 不得不待用鄰接表
第二 對于比較密集的圖 鄰接表無甚優(yōu)勢
第三 如果不需要在稀疏圖中經(jīng)常性的遍歷一個點的所有邊 鄰接矩陣是仍首選的

看到你的輸入數(shù)據(jù)似乎用鄰接矩陣比較好

一點修改 if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue; 中的 12->15

lz是不是寫的麻煩了點
#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 17;

int main() {
int i, a, b, c, d, x, best = -10000, rec = -1, nc, need, np, hun[N], la[N], su[N], dan[N], p[N], sum[4];
char name[N][100];
scanf("%d %d %d", &nc, &need, &np);
for(i = 0; i < nc; i++) {
scanf("%s %d %d %d", &name[i], &p[i], &hun[i], &la[i]);
su[i] = 1-hun[i]; dan[i] = 1-la[i];
}
scanf("%d %d %d %d", &a, &b, &c, &d);
for(x = 0; x < (1<<nc); ++x) {
memset(sum, 0, sizeof(sum));
int price = 0, cnt = 0;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
cnt++; price += p[i];
}

if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
sum[0] += hun[i]; sum[1] += su[i];
sum[2] += la[i]; sum[3] += dan[i];
}

if(sum[0] == a && sum[1] == b && sum[2] == c && sum[3] == d) {
best = price; rec = x;
}
}
for(i = 0; i < nc; i++)
if( (rec & (1<<i)) != 0)
puts(name[i]);
printf("%.2lf\n", 0.8* best / np);
return 0;
}

# 致：byron
也祝你好運
希望有機會來北京看你

這么巧啊 同bless

有一些很好的隨機算法

呵呵 就聊上了啊 :)

Mod4 余數(shù)為0的路徑總數(shù)問題
已知1..n n個點 以及各個點之間的邊以及權(quán) 定義路徑 從1...n并且邊權(quán)之和對4取模為0 求這樣的路徑的個數(shù)
Mod4 余數(shù)為0的最短路徑問題
已知1..n n個點 以及各個點之間的邊以及權(quán) 定義路徑 從1...n并且邊權(quán)之和對4取模 求這樣的路徑中路徑之和最小的路徑

我用了__int64啊

你做的很好了 是我沒有做好 慌張了

首先 我們相當(dāng)于做一個簡單測試（判線段相交的快速排斥實驗的那種味道）我們把所有節(jié)點的入度和出度分別相加 如果入度和和出度和不相等 顯然不滿足圖的要求（因為任意一條邊必然產(chǎn)生一個入度和一個出度）。否則我們定義M = SUM(in-degree); 接下來的任務(wù)是對這M條邊作點的分配。 如果考慮網(wǎng)絡(luò)流的做法，由于每個點對應(yīng)著2個權(quán)值 in-degree, out-degree，一種常規(guī)的做法是將一個點A分成2個點 我們稱為A-in & A-out。然后我們建立一個source連接到所有的A-out點 再建立一個sink連接所有的A-in。這樣我們就可以成功的把indegree和outdegree作為各自的容量。也就是從source到A-out的capacity定為A的out-degree，A-in到sink的capacity定為A的in-degree。為什么要這樣建圖呢？實際上作為任何一個可能存在的邊 在我們的點一分為2之后 都應(yīng)該是從A-out到B-in的這樣一條邊 所以我們這樣建圖之后 就可以對任一點的out到任一點的in連上一條capacity為1的邊（無重邊的題目描述）然后run一次最大流 如果能夠正確得到M的最大流（實際上就會得到M條邊） 這樣就滿足了題目要求了　呵呵　從整個過程來看　這個和二分圖匹配是很像的　實際上　很多題目的網(wǎng)絡(luò)流建圖方案都與２分圖匹配有著關(guān)聯(lián)　^_^

@ares_tc_j:
按你的口氣是看不起做程序設(shè)計競賽的人了
我來說說程序設(shè)計競賽：
1.程序設(shè)計競賽在于鍛煉“腦力”，在熟練掌握各種算法和數(shù)據(jù)結(jié)構(gòu) 常見數(shù)學(xué)模型與方法 解決問題的思維與穩(wěn)健，往往是只一身早早投入項目中的人最最缺乏 也難以得到的珍貴品質(zhì) 往往是突破一般型人才的關(guān)鍵要素
2.參與程序設(shè)計競賽并非拋開項目 相信很多大學(xué)的老師在給項目安排本科生的時候首選的就是代碼能力相對穩(wěn)健的ACM選手 也就是說做程序設(shè)計競賽的人非但不會拋開項目的實踐 而是會在合適的時機全身心的投入進去
樓主寫了一個a+b的程序你看了就鄙視
自己寫了多么了不起的東西啊 空拿室友多么多么怎么怎么管什么用
殊不知 越是不得其真的人越是喜好隨口開河

“就你做的這幾題，真的沒什么可稱道的，所以不要沾沾自喜。”
你就找樓主博客里面的題目試試 看看自己能做幾道？博大精神的圖論算法體系 變幻無窮的計算幾何 300行的寬搜 優(yōu)美的動態(tài)規(guī)劃 人工智能的應(yīng)用 你又了解多少？

“你說做項目？什么是項目？我懷疑呢，因為你現(xiàn)在的水平...........
好好努力吧，不要被別人蒙蔽眼睛。”
我想問問什么叫蒙蔽 你自己醒醒吧

72 if (dist[v] > dist[u] + w)
73 {
74 now.k = dist[u] + w;
75 now.no = v;
76 push(now);
77 dist[v] = dist[u] + w;
78 }
從這段代碼中可以看到 在一次添加節(jié)點后 并沒有按照常理對其他連接的可改進節(jié)點做修正（實際上是模版沒有擴充修改一個節(jié)點的值然后維護堆性質(zhì)的功能） 我們把那些舊的節(jié)點稱為廢節(jié)點的話 所以在選出dist最小的節(jié)點的時候要看看是不是廢節(jié)點 如果是的就要不斷POP出來
while (hs > 0 && h[ 1 ].k > dist[h[ 1 ].no]) pop();
應(yīng)該很好理解了

謝謝提醒 呵呵

題目我是邊做邊找的

很多不懂和不熟悉了的東西要補

可能我自己點擊了200次？

@zzningxp
sorry 我會的

暈倒 我是菜菜。。。

呵呵 各位大牛們見笑了~。。。

o 對 呵呵~~ 我改一下
:)

抱歉 我說的不是很清楚

首先 我這里的p[]數(shù)組代表的時parent 也就是在樹形的并查集中父結(jié)點的標(biāo)號 比如 如果1節(jié)點（根）的子節(jié)點是2，3 則p[2] = p[3] = 1; 而根節(jié)點的父結(jié)點將會被初始化為自己的標(biāo)號 如p[1] = 1;
在樹形的并查集中 我們將根節(jié)點定義為這個集合的代表元
而在這個題目中我們將代表元定義為這個從某一天往上數(shù)第一個空閑的日期 比如 日期
1 2 3 4 5 6 7 8 9 10
如果3是空閑（沒有被分配一個商品）而4，5都已經(jīng)分配 那么p[4]=p[5] = 3;
如果4也是空閑 那么p[3] = 3; p[4] = 4;
這樣 我們在分配商品的時候 要得到從某一天往上數(shù)第一個空閑的日期 就是直接查找這一天所在集合里面的代表元就可以了
從另外一個角度上來看 這個集合其實時一個空閑的天 后面跟著一連串的非空閑天
比如
1 2 3 4 5 6 7 8 9 10
如果3是空閑（沒有被分配一個商品）而4，5都已經(jīng)分配 6沒有分配 那這個集合就是3，4，5 其中代表元為3
以下面這段代碼來作說明吧
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]沒用用過 那么p[d-1]就應(yīng)該=d-1
}
如果flag[g[i].d] is true 代表g[i].d這一天已經(jīng)被分配 于是空閑的天就是find_set(g[i].d);
否則 d = g[i].d; 就是這一天 這個時候集合只有一個元素 就是自己作為代表元
if(d > 0) cnt += g[i].p; 因為有可能代表元為0（設(shè)置數(shù)據(jù)的時候p[d-1]為了不越界 故意留出0） 實際上代表沒有空閑 比如1，2，3，4都滿了 你要放在3的地方 就會得到0 這個位置 所以要>0才能cnt += g[i].p;
flag[d] = 1; 接著把剛才找到的空閑處標(biāo)記
p[d] = p[d-1]; 然后把剛才找到的空閑處的代表元設(shè)置一下
這里的設(shè)置對于下面2中情況都是對的
情況1： 1 2 3 4 5
2空閑 3空閑 我在3處放 然后標(biāo)記p[3] = p[2] = 2;
情況2： 1 2 3 4 5 6
2滿 3滿 4空閑 我在4處放 然后標(biāo)記 p[4] = p[3] = 1
基本上就是這樣了 沒有解釋清楚 真不好意思 :)

p[d]代表選中在D之前第一個空閑的日子
就是說d這個日期用了之后 那么第一個空閑的日子就一定時p[d-1];
也可以這樣寫：
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]沒用用過 那么p[d-1]就應(yīng)該=d-1
}

[quote] "You can assume that each player has made at least two moves, ..."
which means that there must be 4 moves at the beginning :)

太猛了！

6級出來了 比4級低10分。。。呵呵

沒必要寫病毒的說 有什么很大意義么

為什么你可以寫網(wǎng)站，而我現(xiàn)在要一天到晚寫這個BT題目啊……
55555555555555555555555555555……………………

Peking University
Here we imply Peking University ACM Online Judge

呵呵 看了Butterfly Effect 1&2 就是這種感覺~~ 哈哈 沒事啦

of course not

娃哈哈哈 呵呵 豪兄猛阿~~~

呵呵。我K題的速度還真是慢。哈哈