題目鏈接：點擊查看

題目大意：給出n個人和m個雨傘，t分鐘后就要下雨了，現在給出每個人的坐標和速度，以及雨傘所在的坐標，每個雨傘只能容納一個人，題目問最多有多少個人能不被淋到

題目分析：二分圖最大匹配，但是對算法有要求，用匈牙利時間復雜度是O(VE)，會超時，用最大流雖然時間復雜度是O(sqrt(V)E)，但是有N*M*2條邊，會爆內存，所以只能選擇用HK算法，時間復雜度也是O(sqrt(V)E)，空間復雜度是O(NM)

關于HK算法的大牛博客：點擊查看

剩下的就是模板題了，建好圖直接跑模板就好了

代碼：

#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 = 3e3+100;const int M = 3e3+100;int dx[N],dy[M],cx[N],cy[M],dis,n,m;bool vis[M],maze[N][M];bool bfs_findPath() {queue<int> q;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));// 使用BFS遍歷對圖的點進行分層，從X中找出一個未匹配點v// (所有v)組成第一層，接下來的層都是這樣形成——每次查找// 匹配點(增廣路性質)，直到在Y中找到未匹配點才停止查找，// 對X其他未匹配點同樣進行查找增廣路徑(BFS只分層不標記// 是否匹配點)// 找出X中的所有未匹配點組成BFS的第一層dis=inf;for(int i=1;i<=n;++i) {if(cx[i]==-1) {q.push(i);dx[i]=0;}}while(!q.empty()) {int u=q.front();q.pop();if(dx[u]>dis) break;// 該路徑長度大于dis，等待下一次BFS擴充for(int v=1;v<=m;++v) {if(maze[u][v]&&dy[v]==-1) {// (u,v)之間有邊且v還沒有分層dy[v]=dx[u]+1;if(cy[v]==-1) dis=dy[v];// v是未匹配點，停止延伸（查找）,得到本次BFS的最大遍歷層次else {// v是已匹配點，繼續延伸dx[cy[v]]=dy[v]+1;q.push(cy[v]);}}}}return dis!=inf;// 若dis為inf說明Y中沒有未匹配點，也就是沒有增廣路徑了 }bool dfs(int u) {for(int v=1;v<=m;++v) {if(!vis[v]&&maze[u][v]&&dy[v]==dx[u]+1) {vis[v]=1;// 層次（也就是增廣路徑的長度）大于本次查找的dis// 是bfs中被break的情況，也就是還不確定是否是增廣路// 只有等再次調用bfs再判斷(每次只找最小增廣路集)if(cy[v]!=-1&&dy[v]==dis) continue;if(cy[v]==-1||dfs(cy[v])) {// 是增廣路徑，更新匹配集cy[v]=u;cx[u]=v;return true;}}}return false; }int HK() {int ans=0;memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));while(bfs_findPath()) {// 有增廣路memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i) {// 用DFS查找增廣路徑，增廣路徑一定從未匹配點開始// 如果查找到一個增廣路徑，匹配數加一if(cx[i]==-1&&dfs(i)) ++ans;}}return ans; }void init() {memset(maze,false,sizeof(maze)); }struct Node {double x,y,dis; }a[N],b[N];double distance(int x,int y) {return hypot(a[x].x-b[y].x,a[x].y-b[y].y); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init();int time;scanf("%d",&time);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].dis);a[i].dis*=time;}scanf("%d",&m);for(int i=1;i<=m;i++)scanf("%lf%lf",&b[i].x,&b[i].y);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i].dis>=distance(i,j))maze[i][j]=true;printf("Scenario #%d:\n%d\n\n",++kase,HK());}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 2389 Rain on your Parade(Hopcroft-Krap算法求二分图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。