POJ 2112-Optimal Milking-二分答案+二分图匹配

此题有多种做法。

使用floyd算法预处理最短路，二分答案，对于每一个mid，如果距离比mid小就连边，

注意把每个机器分成m个点。这样跑一个最大匹配，如果都匹配上就可以减小mid值。

用的算法比较多但是条理很清晰

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 const int maxn = 300;
 8 const int INF = 0x3f3f3f3f;
 9 int K,C,M;
10 int Map[maxn][maxn];
11 int path[maxn][30*maxn];
12 
13 int floyd()
14 {
15     int i,j,h,t = K+C;
16     for(h=1;h<=t;h++)
17         for(i=1;i<=t;i++)
18             for(j=1;j<=t;j++)
19                 if(Map[i][j] > Map[i][h]+Map[h][j])
20                     Map[i][j] = Map[i][h]+Map[h][j];
21 }
22 
23 int BuildGraph(int mid)
24 {
25     memset(path,false,sizeof path);
26     for(int i=1;i<=C;i++)
27     {
28         for(int j=1;j<=K;j++)
29         {
30             if(Map[K+i][j] <= mid)
31                 for(int h=1;h<=M;h++)
32                 {
33                     path[i][h+(j-1)*M] = true;
34                 }
35         }
36     }
37 }
38 
39 int linker[30*maxn];
40 bool used[30*maxn];
41 
42 int Dfs(int u)
43 {
44     for(int v=1;v<=K*M;v++)
45     {
46         if(path[u][v] && !used[v])
47         {
48             used[v] = true;
49             if(linker[v] == -1 || Dfs(linker[v]))
50             {
51                 linker[v] = u;
52                 return true;
53             }
54         }
55     }
56     return false;
57 }
58 
59 bool MaxMatch()
60 {
61     memset(linker,-1,sizeof linker);
62     for(int i=1;i<=C;i++)
63     {
64         memset(used,false,sizeof used);
65         if(!Dfs(i)) return false;
66     }
67     return true;
68 }
69 
70 void solve()
71 {
72     int low = 1,high = 200*(K+C),mid;
73     while(high > low)
74     {
75         mid = (low+high)/2;
76         BuildGraph(mid);
77         if(MaxMatch()) high = mid;
78         else           low = mid+1;
79     }
80     printf("%d
",low);
81 }
82 
83 int main()
84 {
85     //freopen("input.in","r",stdin);
86     while(~scanf("%d%d%d",&K,&C,&M))
87     {
88         for(int i=1;i<=K+C;i++)
89         {
90             for(int j=1;j<=K+C;j++)
91             {
92                 scanf("%d",&Map[i][j]);
93                 if(Map[i][j] == 0) Map[i][j] = INF;
94             }
95         }
96         floyd();
97         solve();
98     }
99 }