• <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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久午夜伦鲁片免费无码| 国产精品久久久久久久久| www亚洲欲色成人久久精品| 91久久精品无码一区二区毛片| 亚洲狠狠久久综合一区77777| 久久久91人妻无码精品蜜桃HD| 无码国内精品久久综合88| 色88久久久久高潮综合影院| 日本免费久久久久久久网站| 日日狠狠久久偷偷色综合0| 97久久天天综合色天天综合色hd | 久久人人爽人人爽人人AV东京热 | 成人国内精品久久久久影院VR| 合区精品久久久中文字幕一区| 国内精品久久久久影院一蜜桃 | av无码久久久久不卡免费网站| 久久97久久97精品免视看| 东方aⅴ免费观看久久av| 久久99精品久久久久久不卡| 72种姿势欧美久久久久大黄蕉| 日批日出水久久亚洲精品tv| 国产高清美女一级a毛片久久w| 亚洲中文字幕无码久久2017| 色综合久久夜色精品国产| 久久久国产精品| 国内精品伊人久久久久网站| 欧美伊香蕉久久综合类网站| 久久综合九色综合网站| 精品久久久久成人码免费动漫| 久久天天躁狠狠躁夜夜2020| 国产成人精品久久综合| 久久精品免费一区二区三区| 91精品国产色综合久久| avtt天堂网久久精品| 久久一日本道色综合久久| 亚洲∧v久久久无码精品| 精品多毛少妇人妻AV免费久久| 亚洲伊人久久综合影院| 99久久国产精品免费一区二区| 久久亚洲AV无码精品色午夜 | 97精品伊人久久大香线蕉|