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

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

             

            The Perfect Stall
            Time Limit: 1000MS Memory Limit: 10000K
            Total Submissions: 2136 Accepted: 961

            Description

            Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
            Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.

            Input

            The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.

            Output

            For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.

            Sample Input

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

             

            Sample Output

            4

            #include <iostream>

            using namespace std;

            int map[201][201];
            int match[201];
            int visit[201];
            int n,m;

            bool dfs(int p)
            {
                
            int x;
                
            for(x=0;x<m;x++)
                
            {
                    
            if(map[p][x]==1 && visit[x]==-1)
                    
            {
                        visit[x]
            =1;
                        
            int t=match[x];
                        match[x]
            =p;
                        
            if(t==-1 || dfs(t)) return true;
                        match[x]
            =t;
                    }

                }

                
            return false;
            }


            int find_match()
            {
                memset(match,
            -1,sizeof(match));
                
            int i,sum=0;
                
            for(i=0;i<n;i++)
                
            {
                    memset(visit,
            -1,sizeof(visit));
                    
            if(dfs(i)) sum++;
                }

                
            return sum;
            }


            int main()
            {
                
            //freopen("in.txt","r",stdin);
                while(scanf("%d%d",&n,&m)!=EOF)
                
            {
                    
            int i,j;
                    
            for(i=0;i<n;i++)
                        
            for(j=0;j<m;j++) map[i][j]=0;
                    
            for(i=0;i<n;i++)
                    
            {
                        
            int a,b;
                        scanf(
            "%d",&a);
                        
            for(j=0;j<a;j++)
                        
            {
                            scanf(
            "%d",&b);
                            map[i][b
            -1]=1;
                        }

                    }

                    
            int res=find_match();
                    printf(
            "%d\n",res);
                }

                
            return 1;
            }
            參考了郭嵩山的第三冊,用網上的代碼似乎有錯。
            posted on 2007-12-31 12:53 bon 閱讀(238) 評論(0)  編輯 收藏 引用
            Google PageRank 
Checker - Page Rank Calculator
            国产精品热久久无码av| 国产激情久久久久影院老熟女免费 | 99精品久久久久中文字幕| 性欧美丰满熟妇XXXX性久久久| 99久久无色码中文字幕人妻| 精品国产一区二区三区久久| 久久精品无码一区二区日韩AV| 国产成人综合久久精品红| 国产精品99久久久久久人| 久久伊人中文无码| 久久精品国产99国产精品澳门| 久久亚洲中文字幕精品一区四| 2021久久国自产拍精品| 国产成人精品久久| 久久综合久久综合亚洲| 久久91亚洲人成电影网站| 中文无码久久精品| 久久精品中文字幕有码| 久久精品国产99国产电影网| 午夜欧美精品久久久久久久| 久久乐国产综合亚洲精品| 香蕉aa三级久久毛片| 国产无套内射久久久国产| 久久免费小视频| 久久综合丁香激情久久| 精品国际久久久久999波多野| 日本国产精品久久| 久久久久亚洲爆乳少妇无| 亚洲国产天堂久久综合网站| 国产精品一久久香蕉产线看| 中文字幕无码精品亚洲资源网久久| 亚洲国产成人精品91久久久| 久久性精品| 亚洲国产视频久久| 亚洲日本va中文字幕久久| 狠狠精品久久久无码中文字幕| 久久笫一福利免费导航 | 国产精品久久99| 999久久久无码国产精品| 精品国产福利久久久| 国产精品久久久99|