動態(tài)解題報告1112

1、1112 解題題目翻譯：有一群人，群里每個人都認(rèn)識群里的一些人，現(xiàn)在需要將他們分成兩組，分組的條件是：1.2.3.4.每個人都屬于兩隊之一每個隊至少有一個人每個人認(rèn)識其所屬隊里的所有其他人兩隊的人數(shù)盡可能小請找到問題的一個解或者沒有解。原文：Your task is to divide a number ofso two teams, in such a way,t:everyone belongs to one of the teams;every team haseast one member;everyhe team knows every otherson in hi;teams ar

2、e as closeheir sizes assible.This task may have many solutions. You are to find and output any solution, or to reportthe solution does not exist.t題目分析：這道題可以稱得上是一道好題，它同時考查了圖論和DP 的知識。那么這道題該怎么入手呢？首先，分析一下分組的要求：1、把所有的人分成 2 組，每組至少有 1 人；2、每組之間的人兩兩認(rèn)識。非常明顯，如果存在兩個人A 和B，A 不認(rèn)識B，或 B 不認(rèn)識A，那么 A 和B 一定不能分在同一組。因此，以人為

3、結(jié)點(diǎn)重新構(gòu)造一個圖G。假如 A 和B不能分在同一組，那么就在 G 中增加一條無向邊(A,B)。這樣，就得到了一個較為“單純”的模型。下面先研究 G 的對這個模型進(jìn)行簡單分析。通分量 K1。對于這個連通分量，可以先求出 K1 的生成樹T1。對于 K1 中的任意結(jié)點(diǎn)a，假如 a 在T1 中的深度為奇數(shù)，就把a(bǔ) 加入點(diǎn)集 S1；否則 S1,S2 的交集為空。把 a 加入點(diǎn)集 S2（S1,S2 最初為空集）。顯然最后不難證明，如果存在不同結(jié)點(diǎn) p 和 q，p 和 q 同屬于 S1 或 S2，而且 G 中存在邊(p,q) ， 那么要做到滿足題目要求的分組是不可能的， 應(yīng)輸出 Nosolution。否則，

4、組。就得到了連通分量 K1 的唯一分組方案：分為 S1,S2 兩對于G 中的每個連通分量Ki，可以求出相應(yīng)的S1i,S2i。最后，的目的是把全部人分為 2 組。也就是說，對于 i=1,2,3,.,m，須決定把S1i 中的人分到第 1 組，S2i 中的人分到第 2 組，還是做剛好相反的處理。由于題目要求最后兩組的總?cè)藬?shù)差最小可以用動態(tài)規(guī)劃的辦法來確定究竟選取上面的哪種決策。到了這一步，這道題的處理方法就和PKU1015 一樣了。不妨假設(shè)G有m 個連通分量，記|S1i|=xi,|S2i|=yi(i=1,2,3,.,m)。記wi = xi - yi。那么只要對所有的wi 做“半個背包”即可。也就是說

5、，湊出盡量接近sum(wi)的數(shù)。附源代碼：Source CodeProblem: 1112User: zhymaoiingMemory: 412KTime: 188MSLanguage: G+Result: AcceptedSource Code#include #define MAX 105n,g2MAX,gNum,node2MAXMAX,addMAX;boolmapMAXMAX,usedMAX,dpMAX2*MAX,remMAX2*MAX;bool floodfill(x,method)/求解連通分支并分組，分組方法：所有和 x 相連的節(jié)點(diǎn)都和 x 不在同一組i,j;usedx = tr

6、ue;for(i= 1;i = n;i+)if(!usedi & mapxi)for (j = 0;j gmethodgNum;j+) if(mapnodemethodgNumji)return false;nodemethodgNumgmethodgNum+=i;if (!floodfill(i,!method)return false;return true;main()i,x,j,k,l,t; bool fail;scanf(%d,&n);for(i= 1;i = n;i+)scanf(%d,&x);while(x)mapix = true;scanf(%d,&x);for= n;i+)

7、/構(gòu)補(bǔ)圖(i= 1;ifor (j = i+1;j = n;j+)mapji = mapij = (!(mapij &mapji);gNum =0,fail = false;= 1;i = n;i+)for(iif(!usedi)gNum+; node0gNumg0gNum+ = i; if (!floodfill(i,1)fail = true;break;(!fail)/如果分組成功 dp0MAX = true;iffor(i= 1;i = gNum;i+)t = i-1;addi=g0i-g1i;0;j 0;i+,j-)/找差距最(i小的分組方式k = -1;if ifif(dpgNum

8、i) k = i;(dpgNumj) k = j;!= -1)/控制輸出t = gNum,gNum+;(kwhile(t)if (remtk)for (l = 0;lg0t;l+)node0gNumg0gNum+=node0tl;for (l = 0;lg1t;l+)node1gNumg1gNum+=node1tl;k -= addt;elsefor (l = 0;lg0t;l+)node1gNumg1gNum+=node0tl;for (l = 0;lg1t;l+)node0gNumg0gNum+ =node1tl;k += addt;t-;for(l= 0;l 2;l+)prf(%d,glgNum);for (k = 0;k glgNum;k+)prf(%d,ngNumk);phar(n);break;elseprf(No solutionn);P.S.