POJ_2112 二分图多重匹配-蒲公英云

POJ_2112 二分图多重匹配

题意：

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

代码：

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 }