[遞推]CTSC1999 月亮之眼 Moon 解題報告

         IOI1999 中國國家隊選拔賽 月亮之眼
【問題描述】
    吉兒是一家古董店的老闆娘，由於她經營有道，小店開得紅紅火火。昨天，吉兒無意之中得到了散落民間幾百年的珍寶—月亮之眼。吉兒深知“月亮之眼”價值連城：它是由許多珍珠相連而成的，工匠們用金線連接珍珠，每根金線連接兩個珍珠；同時又對每根金線染上兩種顏色，一半染成銀白色，一半染成黛黑色。由于吉兒自小熟讀古籍，所以還曉得“月亮之眼”的神祕傳說：“月亮之眼”原是一個古代寺廟的寶物，原本是掛在佛堂的一根頂樑柱上的，整個寶物垂直懸掛，所有珍珠排成一線，且都鑲嵌在柱子裡，而每一根金線又都是繃緊的，並且金線的銀白色一端始終在黛黑色一端的上方；然而，在一個月圓之夜，“月亮之眼”突然從柱裡飛出，掉落下來，寶物本身完好無損，只是僧侶們再也無法以原樣把“月亮之眼”嵌入柱子中了。吉兒望著這個神祕的寶物，回憶著童年讀到的傳說，頓時萌發出恢復“月亮之眼”的衝動，但是擺弄了幾天依舊沒有成功。

現在，要麻煩您來幫助吉兒完成這項使命。

您要設計一個程序，對於給定的“月亮之眼”進行周密分析，然後給出這串寶物幾百年前嵌在佛堂頂樑柱上的排列模樣。給定的“月亮之眼”有N個珍珠和P根金線，所有珍珠按一定順序有了一個序號：1、2…、N。

 輸入格式 Input Format

輸入資料包含一個“月亮之眼”的特徵描述：

文件第一行有兩個整數N和P，其中N表示寶物中的珍珠個數，P表示寶物中的金線根數；

以下P行描述珍珠連接情況：

文件第I+1行有三個整數，Ri1,Ri2,Li。其中Ri1表示第I根金線的銀白色一端連接的珍珠序號；Ri2表示第I根金線的黛黑色一端連接的珍珠序號；Li表示第I根金線的長度。

輸出格式 Output Format

由於珍珠尺寸很小，所以幾個珍珠可以同時鑲嵌在一個位置上。

您的輸出資料描述的是“月亮之眼”各個珍珠在頂樑柱上的位置，輸出文件共N行：

第I行，一個整數S，它表示標號為I的珍珠在頂樑柱上距離最高位置珍珠的距離。

注意：若無解則輸出僅一行，包含一個整數“-1”。

樣例輸入 Sample Input

9 9

1 2 3

2 3 5

2 7 1

4 5 4

5 6 1

5 9 1

6 7 1

7 8 3

9 8 4

樣例輸出 Sample Output

2 

5 

10

0

4

5 

6 

9

5

時間限制 Time Limitation

1s

來源 Source

IOI99選拔賽試題(ctsc)第二天 problem 2

【分析】

題目描述 真是DT啊！我以為又是在扯淡，結果沒有看題目描述～

 根據題意，可以列出P個方程:

設H[i]為第i個珍珠的的絕對高度、每一個金線銀白色那端連接的珍珠編號為X、黛黑色那端連接的珍珠編號為Y 以及連接X與Y的金線長度為L，由於X在Y上面且金線繃緊，所以H[X]-H[Y]=L。

這樣就列出了P個方程。由於這些方程只能解出每個珍珠的相對位置，所以其絕對位置有無數個解。但是題目只是讓輸出每個珍珠與最高的珠子相距多遠，所以輸出是唯一的，而且是一個非負數。

所以，假設第一個珍珠的絕對高度H[1]=0，從這P個方程中找出與珍珠1有關的方程，然後依次迭代下去，就這樣就可以算出所有珍珠的絕對高度了。

如果計算過程中出現矛盾，直接輸出-1然後exit(0)即可。

接著找出所有珍珠中絕對高度的最大值，用這個最大值減去每一個珍珠的絕對高度即可。

【我的代碼】
我用了隊列（佇列） ，把每個計算出絕對高度的珍珠入隊，然後......

裸代碼RawCode

C++语言: Codee#25412

001 /*
002 *Problem: IOI1999 CTSC Day2-2
003 *Authoe: Yee-fan Zhu
004 *GTalk:zyfworks@gmail.com
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <queue>
009 #define readfile(str) freopen(str,"r",stdin)
010 #define writefile(str) freopen(str,"w",stdout)
011 using namespace std;
012
013 const int MAXN=256;
014 const int MAXP=32386;
015 class LINE
016 {
017 public:
018     int up,down;
019     int h;
020 }Line[MAXP];
021 int H[MAXN];
022 int OK[MAXN];
023 int Checked[MAXP];
024 int N,P;
025
026 void init()
027 {
028     scanf("%d %d\n",&N,&P);
029     for(int i=1;i<=P;i++)
030     {
031         scanf("%d %d %d\n",&Line[i].up,&Line
032
033 [i].down,&Line[i].h);
034     }
035 }
036
037 void Failed()
038 {
039     printf("-1\n");
040     exit(0);
041 }
042
043 void solve()
044 {
045     OK[1]=1;
046     H[1]=0;
047     queue<int>Q;
048     Q.push(1);
049    
050     int t,n,tmp;
051     while(!Q.empty())
052     {
053         t=Q.front();
054         Q.pop();
055         for(int i=1;i<=P;i++)
056         {
057             if(Checked[i])
058                 continue;
059             if(Line[i].up==t)
060             {
061                 n=Line[i].down;
062                 tmp=H[t]-Line[i].h;
063                 if(OK[n] && H[n]!=tmp)
064                     Failed();
065                 H[n]=tmp;
066                 OK[n]=1;
067                 Q.push(n);
068                 Checked[i]=1;
069                 continue;
070             }
071             if(Line[i].down==t)
072             {
073                 n=Line[i].up;
074                 tmp=H[t]+Line[i].h;
075                 if(OK[n] && H[n]!=tmp)
076                     Failed();
077                 H[n]=tmp;
078                 OK[n]=1;
079                 Checked[i]=1;
080                 Q.push(n);
081             }
082         }
083     }
084    
085     int Max=-0x7fffffff;
086     for(int i=1;i<=N;i++)
087         if(H[i]>Max)
088             Max=H[i];
089        
090     for(int i=1;i<=N;i++)
091         printf("%d\n",Max-H[i]);
092 }
093
094 int main()
095 {
096     //readfile("moon.in"),writefile("moon.out");
097     init();
098     solve();
099     return 0;
100 }