POJ_2112 二分图多重匹配

﹏ヽ暗。殇╰゛Y 2023-10-11 09:37 29阅读 0赞

题意：

//题意就是给你k个挤奶池和c头牛，每个挤奶池最多可以来m头牛，而且每头牛距离这k这挤奶池  
//有一定的距离，题目上给出k+c的矩阵，每一行代表某一个物品距离其他物品的位置  
//这里要注意给出的某头牛和某个挤奶池的距离有可能不是最短的，所以这里要用最短路  
//来找出来某个物品到其他物品的最小距离，题目上要求出来在满足每头牛都能到达挤奶池的情况下  
//使所有牛中到达挤奶池中的最大值尽量小  
//全部处理完之后这就是一个二分图多重匹配问题

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<algorithm>
     2 #include<string.h>
     3 #include<stdio.h>
     4 const int INF=0x3f3f3f3f;
     5 using namespace std;
     6 int n,m,k;
     7 int g[300][300],mpp[300][300];
     8 int link[35][20],sum[35],used[35];
     9 void floy()
    10 {
    11     for(int k=1; k<=n+m; k++)
    12     {
    13         for(int i=1; i<=n+m; i++)
    14         {
    15             for(int j=1; j<=n+m; j++)
    16             {
    17                 if(g[i][j]>g[i][k]+g[k][j])
    18                     g[i][j]=g[i][k]+g[k][j];
    19             }
    20         }
    21     }
    22 }
    23 int dfs_solve(int u)
    24 {
    25     for(int i=1; i<=n; i++)
    26     {
    27         if(mpp[u][i]&&!used[i])
    28         {
    29             used[i]=1;
    30             if(link[i][0]<sum[i])
    31             {
    32                 link[i][++link[i][0]]=u;
    33                 return true;
    34             }
    35             for(int j=1; j<=sum[i]; j++)
    36             {
    37                 if(dfs_solve(link[i][j]))
    38                 {
    39                     link[i][j]=u;
    40                     return true;
    41                 }
    42             }
    43         }
    44     }
    45     return false;
    46 }
    47 int hungran()
    48 {
    49     int ans=0;
    50     for(int i=1; i<=n; i++)
    51         link[i][0]=0;
    52     for(int i=1; i<=n; i++)
    53         sum[i]=k;
    54     for(int i=n+1; i<=n+m; i++)
    55     {
    56         memset(used,0,sizeof(used));
    57         if(dfs_solve(i)) ans++;
    58     }
    59     return ans==m;
    60 }
    61 int main()
    62 {
    63     while(~scanf("%d%d%d",&n,&m,&k))
    64     {
    65         for(int i=1; i<=n+m; i++)
    66         {
    67             for(int j=1; j<=n+m; j++)
    68             {
    69                 scanf("%d",&g[i][j]);
    70                 if(g[i][j]==0)
    71                     g[i][j]=INF;
    72             }
    73         }
    74         for(int i=1; i<=n+m; i++)
    75             g[i][i]=0;
    76         floy();
    77         int l=1,r=INF,mid;//题意明明是200是最大距离，可是这里换到210还是错。
    78                           //r还是得开到inf......
    79         while(l<=r)
    80         {
    81             memset(mpp,0,sizeof(mpp));
    82             mid=(l+r)>>1;
    83             for(int i=n+1; i<=n+m; i++)
    84             {
    85                 for(int j=1; j<=n; j++)
    86                 {
    87                     if(g[i][j]<=mid)
    88                         mpp[i][j]=1;
    89                 }
    90             }
    91             if(hungran())
    92                 r=mid-1;
    93             else
    94                 l=mid+1;
    95         }
    96         printf("%d\n",l);
    97     }
    98 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11493029.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif