1、2011 年浙江省省隊選拔賽第一試Overview題目名稱看最小割程序名giftmoviemincut輸入文件名monument.ovie.incut.in輸出文件名monument.outmovie.outmincut.out測試點數目201015每個測試點分值5 分10 分15,1每個 15 分2,3,4,5,6每個 3 分7,8,9,10每個 4 分119 分12,13,14 每個 10 分時間限制2s1s1s空間限制128M128M128M題目類型傳統題傳統題傳統題(gift)的生日就要到了，決定送一件自己親手做工藝品使自己的禮物與眾不同。具體來說已經通過某種方式制作出了一個 pqr

2、的木塊（由pqr 個小木塊組成）。但由于手藝不精，現在這個木塊中的有些小木塊是有問題的(有裂縫、里面是空心等等)，這樣的去的。是不可能直接送出于是決定在這個木塊中再挖出一個 aab 的子木塊(即要求挖出的長方體木塊存在兩條長度相等的相鄰邊)，當然這個子木塊中是不能包含有問題的小木塊的。為了使這個木塊上能包含的圖案，希望從所有可行的方案中挑取 4ab 的值最大的方案。但光檢測木塊中哪些地方有問題就已經耗盡了體力，作為的好友，你能幫幫嗎？【輸入說明】每個輸入文件中僅包含一個測試數據。第一行包含三個由空格隔開的正整數，p,q,r。接下來有 pq 行，每行包含 r 個字符，每個字符只可能是P(Poor

3、) 或者N(Nice)，表示該小木塊有問題或者沒問題。具體的說，第 1+(yp+x-p)行的第z 個字符描述的是坐標為(x,y,z)的小木塊情況。(1=x=p,1=y=q,1=z=r)【輸出說明】輸出文件僅包含一個整數，表示最佳方案的 4ab 的值。【樣例輸入】3 2 5PNNNN PNNNN NPPNP PNNNP NNNNP PPNNP【樣例輸出】24【數據范圍】對于 100%的數據，0p,q,r=150，輸入中至少包含一個N(movie)看到了難得的假期，班上組織大家去看。但由于假期里看的人太多，很難做到讓全班看上同一場，最后大家在一個偏僻的小胡同里找到了一家院。但這家院分配座位的方式很

4、特殊，具體方式如下：1.院的座位共有K 個，并被標號為 1K，每個人買完票后會被隨機指定一個座位，具體來說是從 1K 中等可能的隨機選取一個正整數，設其為 L。2.如果的步驟。L 的座位是空位，則這個座位就分配給此人，否則將 L 加一，繼續前面3.如果在第二步中不存在L 的座位，則該人只能站著看，即所謂的站票。班上共有N 人（包括能夠有座位的概率是多少。自己），作為數學者，想知道全班都【輸入說明】輸入文件第一行有且只有一個正整數T，表示測試數據的組數。第 2T+1 行，每行兩個正整數 N,K，用單個空格隔開，其含義同題目描述。【輸出說明】輸出文件共包含T 行。第i 行應包含兩個用空格隔開的整數

5、 A,B，表示輸入文件中的第 i 組數據的為 A/B。（注意，這里要求將【樣例輸入】31 12 12 2【樣例輸出】1 10 13 4化為既約分數）【數據范圍】對于 20%的數據N,K=10對于 100%的數據T=50,N,K=200最小割(mincut)在圖論課上學到了一個新的概念最小割，下課后寫下了如下這段話：在筆記本上“對于一個圖，某個對圖中結點的劃分將圖中所有結點分成兩個部分，如果結點 s,t 不在同一個部分中，則稱這個劃分是關于 s,t 的割。對于帶權圖來說，將所有頂點處在不同部分的邊的權值相加所得到的值定義為這個割的容量，而 s,t 的最小割指的是在關于 s,t 的割中容量最小的割

6、”現給定一張無向圖，容量不超過x 呢”的疑問，有若干個形如“圖中有多少對點它們的最小割的雖然很想回答這些問題，但最近忙著挖木塊，于是作為仍然是的好友，你又有任務了。【輸入說明】輸入文件第一行有且只有一個正整數T，表示測試數據的組數。對于每組測試數據，第一行包含兩個整數n,m，表示圖的點數和邊數。下面m 行，每行 3 個正整數u,v,c(1=u,v=n,0=c=106)，表示有一條權為 c 的無向邊(u,v)接下來一行，包含一個整數q，表示詢問的個數 下面q 行，每行一個整數x，其含義同題目描述。【輸出說明】對于每組測試數據，輸出應包括 q 行，第 i 行表示第 i 個問題的于點對(p,q)和(q,p)，只統計一次（見樣例）。【樣例輸入】15 010【樣例輸出】10。