首页 > 代码库 > POJ 1548 （二分图+最小路径覆盖）
POJ 1548 （二分图+最小路径覆盖）
题目链接：http://poj.org/problem?id=1548
题目大意：给出一张地图上的垃圾，以及一堆机器人。每个机器人可以从左->右，上->下。走完就废。问最少派出多少个机器人才能捡完所有垃圾。
解题思路：
本题原本是个LIS题。但是有二分图匹配解法。
类似POJ 3020的覆盖题，先不管机器人。把每个点都看作一个中心点。然后从这个点出发，向右、下方向连边，这样这个点就可以看作派出的机器人了。
由于方向固定，怎么连都不会连出反向边，所以是个天然有向图。
跑一遍Hungry，ans=垃圾数-match。
#include "cstdio" #include "vector" #include "cstring" using namespace std; vector<int> G[30*30]; int link[30*30]; bool vis[30*30]; struct point { int x,y; }; bool dfs(int u) { for(int v=0;v<G[u].size();v++) { if(vis[G[u][v]]) continue; vis[G[u][v]]=true; if(link[G[u][v]]==-1||dfs(link[G[u][v]])) { link[G[u][v]]=u; return true; } } return false; } int main() { //freopen("in.txt","r",stdin); point tt; vector<point> pos; int cnt=0,ans=0; while(scanf("%d%d",&tt.x,&tt.y)&&tt.x!=-1&&tt.y!=-1) { if(tt.x==0&&tt.y==0) { for(int i=0;i<cnt;i++) { for(int j=0;j<cnt;j++) { if(i==j) continue; if(pos[i].x<=pos[j].x&&pos[i].y<=pos[j].y) G[i].push_back(j); } } memset(link,-1,sizeof(link)); for(int i=0;i<cnt;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d\n",cnt-ans); cnt=ans=0; pos.clear(); for(int i=0;i<30*30;i++) G[i].clear(); continue; } pos.push_back(tt); cnt++; } }
| 13260799 | neopenx | 1548 | Accepted | 652K | 32MS | C++ | 1361B | 2014-08-06 23:02:14 |
POJ 1548 （二分图+最小路径覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。