題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)牛奶機(jī)器，再給出m只奶牛，每個(gè)機(jī)器只能讓最多k只牛一起擠奶，現(xiàn)在問如何分配奶牛，能讓最遠(yuǎn)的那只奶牛到達(dá)機(jī)器的距離最小

題目分析：很綜合的一道題目了，不算很難，但比較難想，首先看到求最大值的最小值或者求最小值的最大值的這種問題，第一反應(yīng)肯定是二分了，我們可以二分答案，也就是最遠(yuǎn)距離，不過在check之前，我們先要對(duì)給出的鄰接矩陣跑一遍floyd，以保證兩點(diǎn)之間的距離是他們的最短路，這樣才能符合題意，然后我們?cè)撛趺碿heck呢，每次二分出最遠(yuǎn)距離后，對(duì)于最短路小于等于該距離的兩點(diǎn)就可以建邊了，注意！之前二分圖匹配的題比如男孩女孩匹配，建邊的時(shí)候讓男孩指向女孩也行，女孩指向男孩也可以，最后不影響結(jié)果的，但這個(gè)題目不一樣，我們的目的是要讓所有的奶牛能找到一個(gè)機(jī)器，而不是讓所有的機(jī)器都找到一個(gè)奶牛，所以我們這里建邊要用奶牛指向機(jī)器，然后跑匈牙利的時(shí)候也要以奶牛去匹配機(jī)器才行，這里涉及到了一點(diǎn)新知識(shí)，也就是二分圖的多重匹配問題，其實(shí)和單一匹配的思路是一樣的，就是將match[N]變?yōu)榱薽atch[N][N]，就可以了，第一維維護(hù)的是哪個(gè)點(diǎn)，第二維維護(hù)的是有哪些點(diǎn)與之匹配，若當(dāng)前的機(jī)器還沒有匹配夠足夠的奶牛，也就是還沒有達(dá)到上限k，我們就直接將其匹配即可，若達(dá)到了上限，我們就看一下能不能讓其他的奶牛去別的機(jī)器，也就是進(jìn)入dfs尋找增廣路

題外話，因?yàn)閒loydWA了好幾發(fā)，好久沒寫最短路了，也是今天才知道floyd的三層枚舉順序是固定的。。是我太菜了嘛，大概可以這樣理解，最外層枚舉中間斷點(diǎn)k，內(nèi)層枚舉起點(diǎn)i和終點(diǎn)j，相當(dāng)于讓i到j(luò)之間的點(diǎn)不斷松弛，必須固定k不能動(dòng)，不然k一動(dòng)的話答案就錯(cuò)了

具體實(shí)現(xiàn)看代碼吧，應(yīng)該不難懂，三個(gè)很簡單的算法組合出來了這個(gè)題目

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=250;int n,m,limit;vector<int>match[N];//這里我為了方便記錄第二維的長度，用vector代替了二維數(shù)組bool maze[N][N],vis[N];int d[N][N];bool dfs(int x) {for(int i=1;i<=n;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(match[i].size()<limit)//如果當(dāng)前與之匹配的點(diǎn)還沒滿，直接加入即可{match[i].push_back(x);return true;}for(int j=0;j<limit;j++)//否則依次尋找增廣路{if(dfs(match[i][j])){match[i][j]=x;return true;}}}}return false; }bool check(int x) {memset(maze,false,sizeof(maze));//每次跑匈牙利之前都要記得初始化for(int i=1;i<=n;i++)match[i].clear();for(int i=1;i<=n;i++)//建邊f(xié)or(int j=n+1;j<=n+m;j++){if(d[i][j]<=x)maze[j-n][i]=true;}for(int i=1;i<=m;i++)//跑匈牙利{memset(vis,false,sizeof(vis));if(!dfs(i))return false;}return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d%d",&n,&m,&limit)!=EOF){for(int i=1;i<=n+m;i++)for(int j=1;j<=n+m;j++){scanf("%d",&d[i][j]);if(!d[i][j])d[i][j]=inf;}for(int k=1;k<=n+m;k++)//floyd for(int i=1;i<=n+m;i++)for(int j=1;j<=n+m;j++)if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];int l=0,r=inf;int ans;while(l<=r)//二分答案：最遠(yuǎn)距離{int mid=l+r>>1;if(check(mid)){ans=mid;r=mid-1;}elsel=mid+1;}printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 2112 Optimal Milking(二分+二分图最大匹配-多重匹配(修改匈牙利实现)+Floyd求最短路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。