本文主要是介绍UVA10080 Gopher II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n只地鼠(gopher)和m个地洞，现在遇到危险，地鼠要在s秒内钻进地洞里，地鼠的速度是v，但是每个地洞只能容纳1只地鼠。给定每只地鼠和每个地洞的位置，和s,v，求将会有危险的地鼠的个数。
分析：将地鼠看成一个点，所有地鼠看成一个集合X，将地洞看成一个点，所有地洞看成另一个集合Y，如果地鼠能跑到地洞就连一条线，变成二部图，题意就变成了求二部图最大匹配问题了，套用匈牙利算法。
代码：
//uva10080 Gopher II
//AC By Warteac
//2013-4-19
//Runtime:0.036s
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
struct node{float x;float y;node(float a,float b){x = a; y = b;}float distance(node n){return sqrt((y-n.y)*(y-n.y)+(x-n.x)*(x-n.x));}
};
class GopherII{
private:bool map[105][105];//邻接矩阵int nx,ny;//x,y点集的个数bool vis[105];//记录点有无被访问过int link[105];//记录y集合到x集合映射关系int vulgophers;int dfs(int u);int hungary();
public:void initial();void readCase(int);void computing();void outResult();
};
int GopherII::dfs(int u){for(int i=0;i<ny;i++){if(map[u][i]&&!vis[i]){vis[i]=1;if(link[i]==-1||dfs(link[i])){//y值被访问过就到它对应的x值继续向下找增广路link[i]=u;//在递归返回过程中不断修改return 1;}}}return 0;
}
int GopherII::hungary(){//匈牙利算法int ans=0;memset(link,-1,sizeof link);for(int i=0;i<nx;i++){memset(vis,0,sizeof vis);ans+=dfs(i);}return ans;
}
void GopherII::initial(){memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(link,0,sizeof(link));vulgophers = 0;
}
void GopherII::readCase(int n){const double esp = 1e-10;int s,v;float x,y,x2,y2;vector <node> v1,v2;v1.clear();v2.clear();nx = n;cin >> ny >> s >> v;//cout << "s*v = "<<s*v <<endl;for(int i = 0 ; i < nx ; i++){cin >> x >> y;//cout <<"x = "<< x <<"y = "<< y <<endl;v1.push_back(node(x,y));}for(int i = 0 ; i < ny ; i++){cin >> x2 >> y2;//cout <<"x2 = "<< x2 <<"y2 = "<< y2 <<endl;v2.push_back(node(x2,y2));}//cout << "v1.size()= "<<v1.size()<<endl;//cout << "v2.size()= "<<v2.size()<<endl;for(int i = 0; i < v1.size(); i++){for(int j = 0; j < v2.size(); j++){//cout << "v1[i].distance(v2[j]) = " << v1[i].distance(v2[j])<<endl;if(v1[i].distance(v2[j])+esp <= s*v){map[i][j] = 1;//map[j][i] = 1;}}}}
void GopherII::computing(){vulgophers = nx - hungary();
}
void GopherII::outResult(){cout << vulgophers << endl;
}
int main(){GopherII g;int n;while(cin >> n){g.initial();g.readCase(n);g.computing();g.outResult();}}这篇关于UVA10080 Gopher II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
