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

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

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

lz是不是寫的麻煩了點(diǎn)
#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
也祝你好運(yùn)
希望有機(jī)會(huì)來(lái)北京看你

這么巧啊 同bless

有一些很好的隨機(jī)算法

呵呵 就聊上了啊 :)

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

我用了__int64啊

你做的很好了 是我沒(méi)有做好 慌張了

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

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

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

“你說(shuō)做項(xiàng)目？什么是項(xiàng)目？我懷疑呢，因?yàn)槟悻F(xiàn)在的水平...........
好好努力吧，不要被別人蒙蔽眼睛。”
我想問(wèn)問(wè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é)點(diǎn)后 并沒(méi)有按照常理對(duì)其他連接的可改進(jìn)節(jié)點(diǎn)做修正（實(shí)際上是模版沒(méi)有擴(kuò)充修改一個(gè)節(jié)點(diǎn)的值然后維護(hù)堆性質(zhì)的功能） 我們把那些舊的節(jié)點(diǎn)稱為廢節(jié)點(diǎn)的話 所以在選出dist最小的節(jié)點(diǎn)的時(shí)候要看看是不是廢節(jié)點(diǎn) 如果是的就要不斷POP出來(lái)
while (hs > 0 && h[ 1 ].k > dist[h[ 1 ].no]) pop();
應(yīng)該很好理解了

謝謝提醒 呵呵

題目我是邊做邊找的

很多不懂和不熟悉了的東西要補(bǔ)

可能我自己點(diǎn)擊了200次？

@zzningxp
sorry 我會(huì)的

暈倒 我是菜菜。。。

呵呵 各位大牛們見(jiàn)笑了~。。。

o 對(duì) 呵呵~~ 我改一下
:)

抱歉 我說(shuō)的不是很清楚

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

p[d]代表選中在D之前第一個(gè)空閑的日子
就是說(shuō)d這個(gè)日期用了之后 那么第一個(gè)空閑的日子就一定時(shí)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]沒(méi)用用過(guò) 那么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級(jí)出來(lái)了 比4級(jí)低10分。。。呵呵

沒(méi)必要寫病毒的說(shuō) 有什么很大意義么

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

Peking University
Here we imply Peking University ACM Online Judge

呵呵 看了Butterfly Effect 1&2 就是這種感覺(jué)~~ 哈哈 沒(méi)事啦

of course not

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

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