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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            香蕉久久一区二区不卡无毒影院| 国产精品免费久久久久久久久| 久久天天躁狠狠躁夜夜2020老熟妇 | 久久人人爽人人精品视频| 国产精品久久久99| 亚洲国产日韩综合久久精品| 亚洲国产一成人久久精品| 狠狠久久亚洲欧美专区| 久久久久亚洲爆乳少妇无| 中文精品久久久久人妻不卡| 久久国产精品99精品国产987| 久久久久久毛片免费看| 少妇内射兰兰久久| 久久婷婷色综合一区二区| 国内精品伊人久久久久777| 国产 亚洲 欧美 另类 久久| 精品伊人久久大线蕉色首页| 99热成人精品热久久669| 久久91精品国产91| 精品久久久久久国产免费了| 久久久久人妻一区二区三区| 亚洲欧美精品伊人久久| 亚洲国产另类久久久精品 | 国产精品久久久久a影院| 精品久久久久久久久中文字幕| 热久久国产欧美一区二区精品| 亚洲综合精品香蕉久久网97| 97久久婷婷五月综合色d啪蜜芽| 久久综合给合综合久久| 大香网伊人久久综合网2020| 精品无码久久久久国产| 久久亚洲AV成人无码电影| 亚洲精品无码久久毛片| 久久影视综合亚洲| 精品久久久久久久国产潘金莲| 理论片午午伦夜理片久久 | 久久久www免费人成精品| 一本一本久久a久久精品综合麻豆| 国内精品久久久久久久coent| 久久99国产一区二区三区| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 |