首页 > 代码库 > POJ 2536 Gopher II（二分图最大匹配）
POJ 2536 Gopher II（二分图最大匹配）
题意：
N只地鼠M个洞，每只地鼠、每个洞都有一个坐标。
每只地鼠速度一样，对于每只地鼠而言，如果它跑到某一个洞的所花的时间小于等于S，它才不会被老鹰吃掉。
规定每个洞最多只能藏一只地鼠。
问最少有多少只地鼠会命丧鹰口。
思路：
直接建图。二分图最大匹配。
代码：
char st[105];char Range[25][5];int n;int num[10];int cx[25],cy[205];bool bmask[205];vector<int> graph[25];int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,n) cx[i]=-1; rep(i,1,num[5]) cy[i]=-1; rep(i,1,n) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ map<char,int> mp; mp[‘S‘]=1; mp[‘M‘]=2; mp[‘L‘]=3; mp[‘X‘]=4; mp[‘T‘]=5; while(scanf("%s",st)!=EOF){ if(strcmp(st,"ENDOFINPUT")==0) break; scanf("%d",&n); rep(i,1,n) scanf("%s",Range[i]); num[0]=0; rep(i,1,5){ int x; scanf("%d",&x); num[i]=num[i-1]+x; } scanf("%s",st); rep(i,1,n) graph[i].clear(); rep(i,1,n){ int u=mp[Range[i][0]], v=mp[Range[i][1]]; rep(j,num[u-1]+1,num[v]) graph[i].push_back(j); } int dd=MaxMatch(); if(dd>=n) puts("T-shirts rock!"); else puts("I‘d rather not wear a shirt anyway..."); }}
POJ 2536 Gopher II（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。