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

            AOJ 236 Cow Picnic , poj 3256

            Cow Picnic
            Time Limit: 2000 ms   Memory Limit: 64 MB
            Total Submission: 1   Accepted: 1
            Description
            The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

            The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

            Input
            Line 1: Three space-separated integers, respectively: K, N, and M
            Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.
            Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

            Output
            Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

            Sample Input
            2 4 4
            2
            3
            1 2
            1 4
            2 3
            3 4
             

            Sample Output
            2[EOL][EOF]

            Hint
            The cows can meet in pastures 3 or 4.

            Source
            USACO 2006 December Silver 

            從每個牛開始求一次單源最短路徑,假設起點是X,如果從X能到i (di[i]!=INF) ,cnt[i]++,用來統計能到達 i 點的牛的數量。

            結果就是滿足cnt[i]==K的數量,即i點所有的牛都可以到達。

            用spfa求,spfa在這里不是求最段路徑,只要到了就行,不需要是最短的,因此會更快一點。
            #include<iostream>
            #include
            <time.h>
            #include
            <vector>
            #include
            <queue>
            using namespace std;
            const int MAX=1001,INF=0x0fffffff;
            vector
            <int> mp[MAX];
            int d[MAX], cnt[MAX];
            int K,N,M;
            int stay[101];
            void spfa(int x)
            {
                 
            for(int i=1; i<=N; i++)
                         d[i]
            =INF;
                 queue
            <int>q;
                 q.push(x);
                 d[x]
            =0;
                 
            while(q.size())
                 {  
                     
                      
            int u=q.front(); q.pop(); 
                      
            for(int i=0; i<mp[u].size(); i++)
                      {
                              
            if(d[mp[u][i]]==INF)
                              {
                                   d[mp[u][i]]
            =d[u]+1;
                                   q.push(mp[u][i]);
                              }
                      }
                                
                 }
            }

            int main()
            {
                cin
            >>K>>N>>M;
                
                
            for(int i=1; i<=K; i++)
                        cin
            >>stay[i];
                
                
            for(int i=1,s,t; i<=M; i++)
                        {
                                 cin
            >>s>>t;
                                 mp[s].push_back(t);
                        }
                
                
            for(int i=1; i<=K; i++)
                {
                   spfa(stay[i]);    
                   
            for(int i=1; i<=N; i++)
                           
            if(d[i]!=INF)cnt[i]++;   
                }
                
                
            int ans=0;
                
                
            for(int i=1; i<=N; i++)  
                        
            if(cnt[i]==K)ans++;
                
                cout
            <<ans<<endl;        
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-08-30 15:49 田兵 閱讀(400) 評論(0)  編輯 收藏 引用 所屬分類: 圖論題

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            亚洲欧美成人综合久久久| 亚洲精品高清久久| 久久亚洲精品无码AV红樱桃| 国产精品美女久久久网AV| 久久久久久精品无码人妻| 国产婷婷成人久久Av免费高清| 久久久久无码中| 久久九九全国免费| 99久久国产宗和精品1上映| 无码任你躁久久久久久老妇| 国产成人精品久久亚洲高清不卡 | 久久久久18| 久久精品国产91久久麻豆自制| 亚洲人成网亚洲欧洲无码久久| 亚洲一区中文字幕久久| 中文字幕无码免费久久| 国内精品免费久久影院| 久久久久久国产精品免费免费| 久久精品夜夜夜夜夜久久| 国产一区二区三区久久| 国产精品99久久久久久宅男小说| 成人综合久久精品色婷婷| 嫩草影院久久国产精品| 亚洲av日韩精品久久久久久a | 国产美女亚洲精品久久久综合| 丁香狠狠色婷婷久久综合| 成人资源影音先锋久久资源网| 亚洲日本va中文字幕久久| 久久精品aⅴ无码中文字字幕不卡| 久久久久国色AV免费看图片| 国产成人久久精品二区三区| 久久久久久久综合日本亚洲| 久久久久久久亚洲Av无码| 久久久久久亚洲精品成人| 伊人久久综合成人网| 亚洲av成人无码久久精品 | 国产日产久久高清欧美一区| 人妻无码中文久久久久专区| 无码AV波多野结衣久久| 久久久久久国产精品免费无码| 久久久久亚洲av综合波多野结衣|