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

            POJ 1087 C++ (圖論)

            //題目太難懂了,建模比較困難
            //很多人把它做成二分圖
            匹配
            //但貌似用最大流也能求出來
            #include<iostream>
            #include<string>
            #include<map>
            using namespace std;
            int nr,np,na,flag,res,node;
            int arr[402][402];
            int q[1000],pre[1000],used[402];
            map <string,int> PR;

            int path(int s)
            { int u,head,tail,temp,i,j;
              head=tail=0;
              q[tail++]=s;
              used[s]=1;
              while(head<tail)
                   { temp=tail;
                     for(i=head;i<temp;i++)
                         {    u=q[i];
                              if(u==1)
                                 return 1;
                              for(j=0;j<node;j++)
                                 if(used[j]==0 && arr[u][j]>0)
                                    {pre[j]=u;
                                     used[j]=1;
                                     q[tail++]=j;
                                     }
                          }
                      head=temp;
                   }
              return 0;      
            }


            void  ford_fulkerson()
            { int i,j,u,v,min,x,y;
              min=INT_MAX;
              u=pre[1];
              v=1;
              while(u>=0)
                   {if(arr[u][v]<min)
                         min=arr[u][v];
                        v=u;
                        u=pre[u];
                   }
                
              u=pre[1];
              v=1;
              while(u>=0)
                   {   arr[u][v]=arr[u][v]-min;
                       arr[v][u]=arr[v][u]+min;
                       v=u;
                       u=pre[u];
                    }
               res=res+min;       
            }       


            int main()
            {int u,v,w,i,j;
             char str1[25],str2[25];
                   freopen("in.txt","r",stdin);
                   freopen("out.txt","w",stdout);
                     scanf("%d",&nr);
                      flag=0;
                      res=0;
                      node=2;
                      for(i=0;i<nr;i++)
                         { scanf("%s",str1);
                           if(!PR[str1])
                               PR[str1]=node++;
                           arr[0][PR[str1]]++;
                         }
                    
                     scanf("%d",&np);
                     for(i=0;i<np;i++)
                         {  scanf("%s%s",str1,str2);
                             if(!PR[str2])
                                PR[str2]=node++;
                            arr[PR[str2]][1]++;
                         }   
                    
                     scanf("%d",&na);
                     for(i=0;i<na;i++)
                         {   scanf("%s%s",str1,str2);
                             if(!PR[str1])
                                PR[str1]=node++;
                              if(!PR[str2])
                                PR[str2]=node++; 
                              arr[PR[str2]][PR[str1]]=INT_MAX;
                          }    
                      
                     while(!flag)
                         { memset(used,0,sizeof(used));
                           memset(pre,-1,sizeof(pre));
                           if(path(0))
                              ford_fulkerson();
                            else
                              flag=1;
                          }
               printf("%d\n",np-res);  
               return 0;
            }   

            posted on 2008-11-28 14:06 蝸牛 閱讀(1380) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC

            <2008年11月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆分類(20)

            隨筆檔案(20)

            Favorites

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品无码久久久久久午夜| 欧美激情一区二区久久久| 东京热TOKYO综合久久精品| 丁香五月网久久综合| 99精品伊人久久久大香线蕉| 无码乱码观看精品久久| 亚洲精品tv久久久久久久久 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久se精品一区二区| 88久久精品无码一区二区毛片 | 久久国产精品一国产精品金尊| 国产精品一久久香蕉国产线看| 久久久久国产精品嫩草影院| 无码人妻少妇久久中文字幕蜜桃| 午夜不卡888久久| 亚洲精品无码久久久久久| 97精品国产97久久久久久免费| 国产精品乱码久久久久久软件| 狠狠色丁香久久婷婷综| 久久久久久国产a免费观看黄色大片 | 国产2021久久精品| 色婷婷久久久SWAG精品| 久久91综合国产91久久精品| 亚洲熟妇无码另类久久久| 理论片午午伦夜理片久久| 亚洲综合精品香蕉久久网97| 中文字幕无码精品亚洲资源网久久| 国产一区二区精品久久凹凸 | 伊人久久国产免费观看视频| 久久99精品国产99久久6男男| 蜜臀av性久久久久蜜臀aⅴ麻豆| 一本久久a久久精品综合香蕉 | Xx性欧美肥妇精品久久久久久 | 久久精品国产色蜜蜜麻豆| 久久久久亚洲AV成人网人人网站 | 日韩精品国产自在久久现线拍| 中文字幕乱码人妻无码久久| 久久精品国产男包| 中文精品久久久久人妻不卡| 欧美亚洲国产精品久久| 久久久久久久久波多野高潮|