HDU2389 Rain on your Parade 二分匹配 Hopcroft-Carp的算法+模版
这题目过的挺少的，看着吓人，这道题目一开始用最常用的匈牙利算法就超时，后来网上查了一下，原来给忘了二分匹配中还有一个Hopcroft-Carp的算法，直接找了个模版套了一下，1A，好开心
先讲一下题目的意思，第一行案例数，每个案例第一行 代表还有多少单位时间开始下雨，然后是 N个访客，接下来N行是 每个访客的位置（一维坐标平面内）和他的移动速度，接下来M行 代表雨伞数目，接下来M行表示各个雨伞的位置，问在下雨前 最多有多少人能够拿到雨伞（两个人不共用一把伞）
先给个模版把 模版不是我的 来自kuangbin大神 http://www.cnblogs.com/kuangbin/archive/2011/08/12/2135898.html
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[8000];int mp[5012][5012];int num[5012];int lmarry[5012],rmarry[5012];bool vis[5012];int v[5012];int dx[5012],dy[5012];int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m,k;struct Node{int x,y;}l[5012],r[5012];void clear(){memset(lmarry,-1,sizeof(lmarry));memset(rmarry,-1,sizeof(rmarry));memset(vis,false,sizeof(vis));memset(mp,0,sizeof(mp));for(int i=0;i<=m;i++)G[i].clear();}double distance(int i,int j){return sqrt(double((l[i].x-r[j].x)*(l[i].x-r[j].x)+(l[i].y-r[j].y)*(l[i].y-r[j].y)));}bool detal(){queue<int>q;memset(dx,0,sizeof(dx));memset(dy,0,sizeof(dy));int u,v;bool flag=false;for(int i=1;i<=m;i++)if(lmarry[i]==-1)q.push(i);while(!q.empty()){u=q.front();q.pop();for(int i=0;i<G[u].size();i++){v=G[u][i];if(!dy[v]){dy[v]=dx[u]+1;if(rmarry[v]==-1)flag=true;else{dx[rmarry[v]]=dy[v]+1;q.push(rmarry[v]);}}}}return flag;}bool dfs(int x){for(int i=0;i<G[x].size();i++){int v=G[x][i];if(dy[v]==dx[x]+1 && !vis[v]){vis[v]=true;if(rmarry[v]==-1 || dfs(rmarry[v])){rmarry[v]=x;lmarry[x]=v;return 1;}}}return 0;}int main(void){int Case=0;int t;cin>>t;while(t--){printf("Scenario #%d:\n",++Case);scanf("%d",&n);scanf("%d",&m);clear();for(int i=1;i<=m;i++)scanf("%d %d %d",&l[i].x,&l[i].y,&v[i]);scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%d %d",&r[i].x,&r[i].y);for(int i=1;i<=m;i++){for(int j=1;j<=k;j++)if(v[i]*n>=distance(i,j))G[i].push_back(j);}int ans=0;while(detal()){memset(vis,false,sizeof(vis));for(int i=1;i<=m;i++)if(lmarry[i]==-1){if(dfs(i))ans++;}}printf("%d\n\n",ans);}}