• <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 閱讀(239) 評論(0)  編輯 收藏 引用
            Google PageRank 
Checker - Page Rank Calculator
            久久久精品免费国产四虎| 久久久久久夜精品精品免费啦| 一级做a爰片久久毛片16| 青青草国产精品久久| 日批日出水久久亚洲精品tv| 久久久久亚洲AV成人网人人网站| 青草国产精品久久久久久| 久久青青草原精品影院| 内射无码专区久久亚洲| 久久亚洲国产成人精品性色| 亚洲成色999久久网站| 18禁黄久久久AAA片| 亚洲午夜久久久影院伊人| 国产精品久久久久aaaa| 日本久久久久久久久久| 久久精品国产亚洲AV无码麻豆 | 日本精品久久久久影院日本 | 亚洲AV伊人久久青青草原| 久久综合国产乱子伦精品免费| 久久青青草原亚洲av无码| 久久超乳爆乳中文字幕| 久久久久久伊人高潮影院| 久久久久亚洲AV无码专区桃色| 99久久人妻无码精品系列蜜桃| 亚洲欧美日韩精品久久亚洲区| 欧美一区二区精品久久| 人妻精品久久久久中文字幕69 | 久久99精品国产麻豆宅宅| 综合久久国产九一剧情麻豆| 久久久久久亚洲精品不卡| 97久久精品人人做人人爽| 久久这里只精品国产99热| 国产国产成人精品久久| 熟妇人妻久久中文字幕| 久久久午夜精品福利内容| 国产亚洲美女精品久久久| 国产精品99久久精品爆乳| 午夜不卡888久久| 久久国产综合精品五月天| 2020最新久久久视精品爱| 99久久无码一区人妻|