• <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>
            posts - 74,  comments - 33,  trackbacks - 0

            Network of Schools

            Description

            A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
            You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.

            Input

            The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

            Output

            Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

            Sample Input

            5
            2 4 3 0
            4 5 0
            0
            0
            1 0
            

            Sample Output

            1
            2
            

            Source

            IOI 1996
            很好的一道題目寫了一下Tarjan算法求聯(lián)通度,沒想到的是
            #include<cstdio>
            #include
            <cstring>
            #include
            <stack>
            #include
            <vector>
            #define?MAXN?120
            using?namespace?std;
            int?pre[MAXN],low[MAXN],id[MAXN];
            int?cnt,scnt,n,m,k;
            vector
            <int>v[MAXN];
            bool?markin[MAXN],markout[MAXN];
            stack
            <int>ST;
            void?Tarjan(int?x){
            ????
            int?t,i;
            ????
            int?min=low[x]=pre[x]=cnt++;
            ????ST.push(x);
            ????
            for(i=0;i<v[x].size();i++){
            ????????t
            =v[x][i];
            ????????
            if(pre[t]==-1)Tarjan(t);
            ????????
            if(low[t]<min)min=low[t];
            ????}

            ????
            if(min<low[x]){
            ????????low[x]
            =min;
            ????????
            return;
            ????}

            ????
            do{
            ????????id[t
            =ST.top()]=scnt;
            ????????low[t]
            =n;ST.pop();
            ????}
            while(t!=x);
            ????scnt
            ++;
            }

            int?SCC(){
            ????scnt
            =cnt=0;
            ????memset(pre,
            0xff,sizeof(pre));
            ????memset(low,
            0,sizeof(low));
            ????
            for(int?i=0;i<n;i++)
            ????????
            if(pre[i]==-1)Tarjan(i);
            ????
            return?scnt;
            }

            int?main(){
            ????
            int?i,j,a;
            ????
            while(scanf("%d",&n)!=EOF){
            ????????
            for(i=0;i<n;i++)v[i].clear();
            ????????
            for(i=0;i<n;i++){
            ????????????
            while(scanf("%d",&a)&&a)
            ????????????????v[i].push_back(a
            -1);
            ????????}

            ????????k
            =SCC();
            ????????memset(markin,
            0,sizeof(markin));
            ????????memset(markout,
            0,sizeof(markout));
            ????????
            int?sum_F=0,sum_S=0;
            ????????
            for(i=0;i<n;i++)
            ????????????
            for(j=0;j<v[i].size();j++)
            ????????????????
            if(id[i]!=id[v[i][j]]){
            ????????????????????markout[id[i]]
            =true;
            ????????????????????markin[id[v[i][j]]]
            =true;
            ????????????????}

            ????????
            for(i=0;i<k;i++){
            ????????????
            if(!markin[i])sum_F++;
            ????????????
            if(!markout[i])sum_S++;
            ????????}

            ????????printf(
            "%d\n",sum_F);
            ????????
            if(sum_F==1&&sum_S==1)printf("0\n");
            ????????
            else?printf("%d\n",sum_F>sum_S?sum_F:sum_S);
            ????}

            }

            這樣是錯(cuò)的,不知道為什么 ,最后把if(sum_F==1&&sum_S==1)printf("0\n");
            改成了if(k==1)printf("0\n");就AC了。實(shí)在是不懂為什么呢 ,其實(shí)這兩個(gè)條件應(yīng)該是等價(jià)的
            當(dāng)最后縮成只有一個(gè)點(diǎn)的時(shí)候必然存在sum_F入度等于出度sum_S等于1。
            所以說比較郁悶。。。。
            posted on 2009-05-13 16:45 KNIGHT 閱讀(202) 評(píng)論(1)  編輯 收藏 引用

            FeedBack:
            # re: Network of Schools
            2009-05-14 07:24 | Knight
            感謝zju的HH神牛,謝謝 HH神牛的數(shù)據(jù)2個(gè)點(diǎn) a->b
            2
            2 0
            0
            對于in==1&&out==1但是scc==2


              回復(fù)  更多評(píng)論
              

            只有注冊用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            精品久久久久久无码中文野结衣| 久久夜色精品国产网站| 国产精品久久久久久久午夜片 | 狠狠色婷婷久久一区二区三区| 久久久精品国产sm调教网站| 国产三级观看久久| 亚洲国产精品无码久久青草 | 国产高潮国产高潮久久久91 | 久久久久18| 国产婷婷成人久久Av免费高清| 国产精品久久久99| 久久久久久久亚洲Av无码| 久久精品中文字幕有码| 国产精品岛国久久久久| 国产精品久久久久免费a∨| 一级做a爰片久久毛片16| 久久人人爽人人爽人人片av麻烦| 国产高清美女一级a毛片久久w| 亚洲午夜久久久久久久久久 | 国产精品伊人久久伊人电影 | 草草久久久无码国产专区| 亚洲精品tv久久久久久久久| 人妻少妇精品久久| 久久精品国产99国产精品| 草草久久久无码国产专区| 久久国产精品国产自线拍免费| 久久人爽人人爽人人片AV| 久久婷婷五月综合色奶水99啪| 久久久久一级精品亚洲国产成人综合AV区| 99久久久精品免费观看国产| 欧美亚洲色综久久精品国产| 亚洲欧美一区二区三区久久| 久久久WWW成人免费毛片| 精品熟女少妇aⅴ免费久久| 日本道色综合久久影院| 久久亚洲欧美日本精品| 一本大道加勒比久久综合| 99久久精品国产一区二区蜜芽| 99久久精品国产综合一区| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 亚洲乱亚洲乱淫久久|