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
时间: 10-05

POJ 1548 (二分图+最小路径覆盖)的相关文章

poj 3020 二分图最小路径覆盖

二分图最小路径覆盖=|v|-最大匹配.此题为有向图,切所有边正反向存了两遍,所以结果匹配数要除以2 // // main.cpp // poj3020 // // Created by Fangpin on 15/5/29. // Copyright (c) 2015年 FangPin. All rights reserved. // #include <iostream> #include <cstdio> #include <vector> #include <

Taxi Cab Scheme POJ - 2060 二分图最小路径覆盖

Running a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible,there is also a need to schedule all the taxi rides whi

POJ 3020 (二分图+最小路径覆盖)

题目链接:http://poj.org/problem?id=3020 题目大意:读入一张地图.其中地图中圈圈代表可以布置卫星的空地.*号代表要覆盖的建筑物.一个卫星的覆盖范围是其周围上下左右四个点.问最少需要几个卫星才能覆盖所有建筑物. 解题思路: 有点类似POJ 1328的覆盖题,不过那题比较简单可以贪心.这题你可以YY试试. 覆盖问题其实可以用图论解决.这题就属于最小路径覆盖,手动由一个点出发连一些路径,这样Hungry就能求出最少需要多少这样的中心点,就可以达成目标了. 本题最大的疑问是

POJ 2594 二分图最小路径覆盖

点击打开链接 题意:将所有点都连起来至少需要多少条路径 思路:二分图的最小路径覆盖,而最小路径覆==图的顶点数-图的最大匹配,而当初还学习过最小顶点覆盖==最大匹配,而最小顶点覆盖需要连双向边,结果除以2,那是因为1-->2时,点1和点2都已经用过,所以我在连一个相应的一条边,代表这两个点不能在用了,样例详见hdu 1054 第二组.而接下来的求最小路径覆盖的最大匹配我们就只能是单向的,这个为什么可以避免呢,因为1-->2-->3这样的话,最小路径为1,但是转化为二分图上的话,对应的点2

POJ 1422 DAG最小路径覆盖

求无向图中能覆盖每个点的最小覆盖数 单独的点也算一条路径 这个还是可以扯到最大匹配数来,原因跟上面的最大独立集一样,如果某个二分图(注意不是DAG上的)的边是最大匹配边,那说明只要取两个端点只要一条边即可. 故最小覆盖数还是 顶点数-最大匹配数 根据DAG建图的时候,就是DAG有边就给对应的端点建边 #include <iostream> #include <cstdio> #include <cstring> using namespace std; int d[15

POJ3216 Repairing Company【二分图最小路径覆盖】【Floyd】

题目链接: http://poj.org/problem?id=3216 题目大意: 有Q个地点,告诉你Q个地点之间的相互距离(从i地点赶到j地点需要的时间).有M项任务, 给你M项任务所在的地点block.开始时间start和任务完成需要时间time.一个工人只有在 他准备完成的下一项任务开始之前完成手上的任务,然后在下一项任务开始之前赶到下一项 任务的地点,才能完成这两项任务.问:最少需要多少个工人来完成这M项任务. 思路: 先用Floyd算出Q个地点之间相互最短距离.然后建立一个二分图,每

POJ2594 Treasure Exploration【二分图最小路径覆盖】【Floyd】

题目链接: http://poj.org/problem?id=2594 题目大意: 给你N个地点,M条有向边,已知构成的图是有向无环图.现在要在地点上放机器人通过M 条边来遍历N个地点,问:最少需要多少个机器人可以遍历N个地点. 思路: 这是一道求最小路径覆盖的题目.和一般最小路径覆盖的题目不一样的地方是:这里的点可 以重复遍历.也就是可以有两个及以上的机器人经过同一个点. 那么,先建立一个二分图, 两边都为N个地点.然后在原图的基础上,用Floyd求一次传递闭包,也就是如果点i可以到达 点j

POJ1422 Air Raid【二分图最小路径覆盖】

题目链接: http://poj.org/problem?id=1422 题目大意: 有N个地点和M条有向街道,现在要在点上放一些伞兵,伞兵可以沿着有向街道走,直到不能走为止. 每条边只能被一个伞兵走一次.问:至少放多少伞兵,能使伞兵可以走到图上所有的点. 思路: 很明显的最小路径覆盖问题.先转换为二分图,先将N个点每个点拆成两个点,左边是1~N个点,右 边也是1~N个点.将有向街道变为左边点指向右边点的边. 因为二分图最小路径覆盖 = 点数 - 二分图最大匹配数,则求出结果就是放的最少伞兵数.

HDU1151_Air Raid(二分图/最小路径覆盖=n-最大匹配)

解题报告 题目传送门 题意: 一个小镇,所有的街道都是单向的,这些街道都是从一个十字路口通往另一个十字路口,已知从任何十字路口出发,沿着这些街道行走,都不能回到同一个十字路口,也就是说不存在回路. 计算攻击这个小镇需要派的伞兵最少数目,这些伞兵要走遍小镇的所有十字路口,每个十字路口只由一个伞兵走到.每个伞兵在一个十字路口着陆,沿着街道可以走到其他十字路口. 思路: 用最小的伞兵覆盖街道,最小路径覆盖模型.把每个点拆成X1,Y1,这样建成二分图.最小路径覆盖=n-最大匹配数. #include <

POJ 1422 &amp;&amp; ZOJ 1525 --Air Raid【二分图 &amp;&amp; 最小路径覆盖】

Air Raid Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 7451   Accepted: 4434 Description Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an i