• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku 3687 Labeling Balls 逆向拓撲!注意

            英文太短,直接貼

            Description

            Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:

            1. No two balls share the same label.
            2. The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".

            Can you help windy to find a solution?


            Input

            The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, bN) There is a blank line before each test case.

            Output

            For each test case output on a single line the balls' weights from label 1 to label N. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... If no solution exists, output -1 instead.

            然后這題是一個裸的拓撲排序,但是輸出有點忽悠人,要求輸出標簽代表的球的重量,按照標簽號排序,而且對于重復情況需要標簽ID小的球的質量盡量小。
            這里有一個錯誤折騰死人,如果按照正向拓撲,給標簽號小的標簽分配給質量小的球是不對的,應為對于拓撲序來說,很多鏈是平行的,給鏈頭元素最小值的貪心策略并不能保證全局最小,如下圖兩條平行鏈,如果給3分配了較小質量的球,1就得不到最小質量的球,導致結果不滿組最優,但是如果逆向拓撲,給鏈頭標簽最大的分配最重的物體一定能保證正向拓撲序最小
            4 2 5
            3 1
             1 # include <cstdio>
             2 # include <queue>
             3 # include <vector>
             4 # include <cstring>
             5 using namespace std;
             6 priority_queue<int,vector<int>,less<int> >q;
             7 int g[205],degree[205];
             8 int nxt[50000],v[50000],c,n,m;
             9 int ans[205],num;
            10 int main()
            11 {
            12     int testcase;
            13     scanf("%d",&testcase);
            14     while(testcase--)
            15     {
            16         memset(g,-1,sizeof(g));
            17         memset(degree,0,sizeof(degree));
            18         c=num=0;
            19     while(!q.empty()) q.pop();
            20         scanf("%d%d",&n,&m);
            21         while(m--)
            22         {
            23             int a,b;
            24             scanf("%d%d",&a,&b);
            25             v[c]=a;
            26             nxt[c]=g[b];
            27             g[b]=c++;
            28         degree[a]++;
            29         }
            30         for(int i=1;i<=n;i++)
            31             if(!degree[i])
            32                 q.push(i);
            33     num=n;
            34         while(!q.empty())
            35         {
            36             int top=q.top();
            37             q.pop();
            38             ans[top]=num--;
            39             for(int p=g[top];p!=-1;p=nxt[p])
            40             {
            41                 degree[v[p]]--;
            42                 if(!degree[v[p]])
            43                     q.push(v[p]);
            44             }
            45         }
            46         if(num>0)
            47             printf("-1\n");
            48         else
            49         {
            50             printf("%d",ans[1]);
            51             for(int i=2;i<=n;i++)
            52           printf(" %d",ans[i]);
            53             printf("\n");
            54         }
            55     }
            56     return 0;
            57 }

            posted on 2010-10-22 02:24 yzhw 閱讀(155) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久亚洲精品中文字幕| 国产91久久精品一区二区| 久久国产视屏| 久久综合亚洲色一区二区三区| 亚洲国产欧洲综合997久久| 狠狠色丁香久久婷婷综| 欧美久久一区二区三区| 精品乱码久久久久久久| 久久精品国产一区二区三区| 久久伊人五月丁香狠狠色| 国产精品久久国产精麻豆99网站| 国产精品成人久久久久三级午夜电影 | 青青草原综合久久大伊人导航 | 精品久久久久久久无码| 精品无码久久久久久国产| 久久香综合精品久久伊人| 伊人伊成久久人综合网777| 久久精品国产69国产精品亚洲| 伊人久久一区二区三区无码| 伊人丁香狠狠色综合久久| 日日躁夜夜躁狠狠久久AV| 亚洲国产精品综合久久网络| 狠狠色综合久久久久尤物| 久久国产精品久久精品国产| 亚洲欧美成人综合久久久| 亚洲精品无码久久毛片| 久久久久无码中| 国产精品99久久精品爆乳| 久久婷婷国产麻豆91天堂| 日韩AV无码久久一区二区| 99久久香蕉国产线看观香| 亚洲国产精品无码久久青草| 亚洲成av人片不卡无码久久| 精品人妻伦九区久久AAA片69| 久久99国产精品久久99| 精品久久久久久综合日本| 精品国产一区二区三区久久久狼 | 国产精品九九久久免费视频| 久久99久久99小草精品免视看| 1000部精品久久久久久久久| 久久久无码精品亚洲日韩按摩 |