圖論練習題 圖的平方 ljb

【問題描述】

有向圖G=(V,E)的平方是圖G^2=(V,E^2)，該圖滿足下列條件：(u,w)∈E^2當且僅當對v∈V，有(u, v)∈E，且(v,w)∈E。亦即，如果圖G中頂點u和w之間存在著一條恰包含兩條邊的路徑時，則G^2必包含該邊(u,w)。

請編程序對於給定的有向圖G，查詢邊(u,w)是否存在於平方圖G^2中。

【輸入文件】

第一行有兩個整數，v(1<=v<=100000)，m(1<=m<=1000)，其中v表示圖G的頂點個數，（頂點按1~v編號）；

接下來有m行，每行包含4個整數u1,u2,v1,v2，表示在圖G中，頂點區間[u1,u2]中的每一個頂點至頂點區間[v1,v2]中的每一個頂點都有邊相連；

接下來有一行，一個整數n（1<=n<=1000），表示查詢的個數；

接下來有n行，每一行有4個整數，x1,x2,y1,y2，表示一個詢問，即詢問在平方圖G^2中，其頂點區間[x1,x2]中的每一個頂點至頂點區間[y1,y2]中的每一個頂點是否都有邊。

圖論練習題 摔跤 rassle 題解

【問題描述】

有兩種類型的職業摔跤手：一種是“好選手”，另一種是“差選手”。對於任何一對職業摔跤手來說，他們中可能有、也可能沒有比賽。假定有 n 位職業摔跤手，並且有一份清單，上面列出了 r 對參加比賽的摔跤手。寫一個程序,它能夠確定是否可能指定某些摔跤手為好選手，而將餘下的摔跤手指定為壞選手，從而使得每一場比賽都是在一個好選手與一個差選手之間進行。如果有可能做出這樣的指定，你的程序就應該將它產生出來，否則輸出無解“No”。

【輸入格式】

第1行有三個整數n，r。n是職業摔跤手的數量，r是比賽場數，它們之間用一個空格隔開。

接下來的r行，每行用兩個數V1，V2表示V1號摔跤手與V2號摔跤手比賽，選手從1開始編號。

【輸出格式】

輸出有兩行，第一行“好選手”的編號，第二行為“差選手”的編號，編號之間用一個空格隔開。

注意：為了鼓勵選手，使輸出答案唯一，請儘量多的將選手設為“好選手”，並且在可行條件下選擇編號小的選手為“好選手”。

如果無解，則輸出一行“No”。

動態規劃練習題 相似基因 gene 題解

問題描述

大家都知道，基因可以看作一個鹼基對序列。它包含了 4 種核苷酸，簡記作 A,C,G,T 。生物學家正致力於尋找人類基因的功能，以利用於診斷疾病和發明藥物。

在一個人類基因工作組的任務中，生物學家研究的是：兩個基因的相似程度。因為這個研究對疾病的治療有著非同尋常的作用。兩個基因的相似度的計算方法如下：

對於兩個已知基因，例如 AGTGATG 和 GTTAG ，將它們的鹼基互相對應。當然，中間可以加入一些空鹼基 - ，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

這樣 , 兩個基因之間的相似度就可以用鹼基之間相似度的總和來描述，鹼基之間的相似度如下表所示：

那麼相似度就是： (-3)+5+5+(-2)+(-3)+5+(-3)+5=9 。因為兩個基因的對應方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度為： (-3)+5+5+(-2)+5+(-1)+5=14 。規定兩個基因的相似度為所有對應方法中，相似度最大的那個。

[搜索]ACM練習題：分球 ball 解題報告

題目來源：
1. 浙江理工大學 OnlineJudge 2584
2. 山東理工大學 OnlineJudge 1406

【問題描述】

在一個裝滿財寶的屋子裡，有2N個盒子排成一排。除了兩個相鄰的空盒外，其餘的每個盒子裡都裝有一個金球或者一個銀球，總共有N-1個金球和N-1個銀球。用圖6．3所示為一個N=5時的例子，G表示金球，S表示銀球。

G

S

S

G

G

S

G

S

任意兩個相鄰的非空的盒子裡的球可以移動到兩個相鄰的空盒中，移動不能改變這兩個球的排列順序。寫一個程序，用最少的移動次數把所有的金球都移到所有的銀球的左邊。

【拓撲排序練習題】課程安排問題 curriculum

【問題描述】

一個軟體專業的學生必須學習一系列基本課程，其中有些課程是基礎課，它獨立於其它課程，如《高等數學》、《計算引論》；而另一些課程必須在學完作為它的基礎的先修課程才能開始。如，在《程序設計基礎》和《離散數學》學完之前就不能開始學習《資料結構》。這些先決條件定義了課程之間的領先（優先）關係。請你在符合上述領先（優先）條件的前提下，給出所有課程的一個有序序列，以方便學校排課。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n(0<n<=100)門課程

第2--n+1行分別表示第1--n門課程的先修課程資訊，每行有若干個整數m,s1,s2,...,sm

m表示該門課程有m門先修課程，s1,s2,...,sm分別表示m門先修課的編號，如果該門課沒有先修課程，則m為0。

【輸出格式】

一行，n個整數，表示n門課程編號的有序序列(如果這樣的序列不存在，則輸出no;如果有多個這樣的序列，輸出字典序最小的)

【強連通分量】四面楚歌 virus 解題報告

【題目描述】

公元2008年10月31日星期五，篤志者所在的整個機房由於猖獗的病毒一片恐慌。經查證，病毒是由A1機器散播開來的。。這要追溯到29日，篤志者由於病毒被迫從A1機器撤離。

一想到病毒是從自己的機器傳開的，篤志者就心神不寧。他決定搞清楚病毒是怎麼散播開來的。事實上，機房內的機器並不是全部都能夠互相感染的。篤志者（ceeji）好不容易經過測試得到了機房中各機器間是否連通的圖表，就在他馬上就要得出結果的時候，大腦突然亂了！問題的嚴重性在於：如果他不在1s內搞清楚這個問題，機房就會整體癱瘓。現在篤志者求助於你，他需要知道病毒從未感染機房開始，最少入侵幾臺機器之後，機房就會整體感染。

【輸入格式】

文件的第一行為一個整數n，第二行至第n+1行為n*n的矩陣（若第i行第j列為1，則機器i能對機器j進行ARP攻擊（即感染機器j），若第i行第j列為0，則機器i不能感染機器j）。

文件名為“2.in”。

【輸出格式】

輸出文件只有一行，為篤志者想知道的最少感染機器數。

文件名為“2.out”。