• <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);
            ????}

            }

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

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


              回復(fù)  更多評論
              

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


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

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品高清国产一线久久 | 久久久久无码专区亚洲av| 人妻久久久一区二区三区| 久久影院综合精品| 国产AV影片久久久久久| 久久亚洲AV无码精品色午夜麻豆| 亚洲国产精品无码久久一区二区| 囯产精品久久久久久久久蜜桃 | 免费观看成人久久网免费观看| 午夜视频久久久久一区 | 久久国产色AV免费看| 欧美精品丝袜久久久中文字幕 | 国产成人久久久精品二区三区| 欧美一级久久久久久久大| 97久久综合精品久久久综合| 三级三级久久三级久久 | 漂亮人妻被中出中文字幕久久| 精品熟女少妇a∨免费久久| 国内精品久久久久影院薰衣草 | 久久精品国产亚洲AV不卡| 久久这里只有精品视频99| 国产一区二区三区久久| 亚洲精品乱码久久久久久中文字幕| 91久久精品电影| 99久久综合狠狠综合久久| 久久综合噜噜激激的五月天| 久久乐国产综合亚洲精品| 热久久国产欧美一区二区精品 | 四虎影视久久久免费| 精品久久久无码中文字幕| 97久久精品午夜一区二区| 99久久夜色精品国产网站| 中文精品久久久久人妻| 亚洲欧美国产日韩综合久久| 99久久www免费人成精品| 女人香蕉久久**毛片精品| AV色综合久久天堂AV色综合在| 精品久久久久久亚洲精品 | 久久久久久精品免费免费自慰| 一本大道久久香蕉成人网| 亚洲国产精品一区二区三区久久|