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啊

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

首先 我們相當于做一個簡單測試（判線段相交的快速排斥實驗的那種味道）我們把所有節(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ù)學模型與方法 解決問題的思維與穩(wěn)健，往往是只一身早早投入項目中的人最最缺乏 也難以得到的珍貴品質(zhì) 往往是突破一般型人才的關(guān)鍵要素
2.參與程序設(shè)計競賽并非拋開項目 相信很多大學的老師在給項目安排本科生的時候首選的就是代碼能力相對穩(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é)點的標號 比如 如果1節(jié)點（根）的子節(jié)點是2，3 則p[2] = p[3] = 1; 而根節(jié)點的父結(jié)點將會被初始化為自己的標號 如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; 接著把剛才找到的空閑處標記
p[d] = p[d-1]; 然后把剛才找到的空閑處的代表元設(shè)置一下
這里的設(shè)置對于下面2中情況都是對的
情況1： 1 2 3 4 5
2空閑 3空閑 我在3處放 然后標記p[3] = p[2] = 2;
情況2： 1 2 3 4 5 6
2滿 3滿 4空閑 我在4處放 然后標記 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題的速度還真是慢。哈哈