<span>HDU2389 Rain on your Parade（HK模版）</span>
题意：
在一个二维坐标系上有n个人和m把伞，每个人都有自己的移动速度，
问有多少人可以在s min内移动到不同的雨伞处（不允许两个人共用一把伞）。
思路：
由于nm太大（3000），匈牙利会超时，就用HK算法
整理了HK的模版
/* *********************************************** //Author :devil //Created Time :2016/5/10 23:13:51 //************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; const int N=3010; const int inf=0x3f3f3f3f; vector<int>eg[N]; int ax[N],ay[N],as[N],bx[N],by[N],n,m; int mx[N],my[N]; int dx[N],dy[N],dis; bool vis[N]; bool bfs() { queue<int>q; dis=inf; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(int i=0;i<n;i++) if(mx[i]==-1) { q.push(i); dx[i]=0; } while(!q.empty()) { int u=q.front(); q.pop(); if(dx[u]>dis) break; for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(dy[v]==-1) { dy[v]=dx[u]+1; if(my[v]==-1) dis=dy[v]; else { dx[my[v]]=dy[v]+1; q.push(my[v]); } } } } return dis!=inf; } bool dfs(int u) { for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(!vis[v]&&dy[v]==dx[u]+1) { vis[v]=1; if(my[v]!=-1&&dy[v]==dis) continue; if(my[v]==-1||dfs(my[v])) { my[v]=u; mx[u]=v; return 1; } } } return 0; } int MaxMatch() { int ans=0; memset(mx,-1,sizeof(mx)); memset(my,-1,sizeof(my)); while(bfs()) { memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) if(mx[i]==-1&&dfs(i)) ans++; } return ans; } int main() { //freopen("in.txt","r",stdin); int t,s,cas=0; scanf("%d",&t); while(t--) { for(int i=0;i<=3000;i++) eg[i].clear(); scanf("%d%d",&s,&n); for(int i=0;i<n;i++) scanf("%d%d%d",&ax[i],&ay[i],&as[i]); scanf("%d",&m); for(int i=0;i<m;i++) scanf("%d%d",&bx[i],&by[i]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if((ax[i]-bx[j])*(ax[i]-bx[j])+(ay[i]-by[j])*(ay[i]-by[j])<=as[i]*as[i]*s*s) eg[i].push_back(j); printf("Scenario #%d:\n",++cas); printf("%d\n\n",MaxMatch()); } return 0; }
联想工作强度 161人发布