`
暴风雪
  • 浏览: 390906 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[最小路径覆盖]poj 2594:Treasure Exploration

阅读更多

大致题意:

    给出一个由n个顶点m条边组成的无回路有向图。求最少可以同时存在多少路径,使得这些路径可以覆盖所有的点(注:每个都点可以被多条路径覆盖)。

 

大致思路:
    最小路径覆盖的一点小小变形,由于这里的点可以被重复覆盖,所以除了按照普通求最小路径覆盖的方式建立二分图以外,还要对原图用floyd求一遍传递闭包,并更新二分图。接下来用点数n减去最大匹配得到的就是答案。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
int c,d;
int map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];

int dfs(int s){
    for(int i=1;i<=d;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}

void floyd(int n){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(map[i][k]&&map[k][j]){
                    map[i][j]=1;
                }
            }
        }
    }
}
int main(){
    int n,m,a,b,ans,i,j;
    while(scanf("%d%d",&n,&m)&&(n||m)){
        c=d=n;
        ans=0;
        memset(map,0,sizeof(map));
        while(m--){
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        floyd(n);
        memset(linkk,-1,sizeof(linkk));
        for(i=1;i<=c;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}
 

 

0
0
分享到:
评论

相关推荐

    经典 的POJ 分类

    - POJ 1860、POJ 3259:利用Dijkstra算法解决最短路径问题。 - POJ 1062、POJ 2253:涉及Bellman-Ford算法的应用场景。 - POJ 1125、POJ 2240:Floyd算法的典型实例。 ##### 最小生成树 - **算法**: - Prim...

    acm新手训练方案新手必备

    - POJ 2240: 特殊条件下的最短路径 - **最小生成树**:Prim算法、Kruskal算法等。 - **示例题目**: - POJ 1789: Prim算法应用 - POJ 2485: Kruskal算法实例 - POJ 1258: 最小生成树问题 - POJ 3026: 最小生成...

    POJ2092:计数排序,求第K大的元素

    【标题】"POJ2092:计数排序,求第K大的元素"是一个编程题目,主要涉及计数排序算法以及如何在数组中找出第K大的元素。计数排序是一种非基于比较的排序算法,它适用于整数排序,尤其在数据范围不大的情况下效率极高。...

    poj 3593 Sea Base Exploration.md

    poj 3593 Sea Base Exploration.md

    acm训练计划(poj的题)

    - (poj1789, poj2485, poj1258, poj3026):介绍普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal),用于寻找加权无向图的最小生成树。 4. **拓扑排序**: - (poj1094):适用于有向无环图(DAG)的一种排序方式,...

    ACM北大训练

    - poj1062: 涉及寻找两点间的最短路径,可用Dijkstra算法解决。 - poj2253: 可能涉及负权边,适合用 Bellman-Ford 算法解决。 ##### 3. 最小生成树算法 - **定义**: Prim 和 Kruskal 算法用于在加权无向图中寻找...

    POJ1-7试题

    这是西北工业大学的POJ试题的答案,欢迎下载!

    poj题目分类

    * 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、...

    poj部分水题代码

    根据提供的文件信息,我们可以从中...以上四个题目覆盖了不同的编程技巧和算法思想,如条件判断、循环结构、数学计算及字符串操作等。对于初学者来说,这些题目不仅能够帮助他们巩固基础知识,还能提升解决问题的能力。

    poj刷题指南

    网上整理的一些poj刷题指南。 poj地址:http://poj.org

    poj训练计划.doc

    - 最短路径算法:如Dijkstra算法和Bellman-Ford算法,用于找到两点间的最短路径,如`poj1062, poj2253`。 - 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑...

    ACM-POJ 算法训练指南

    1. **最短路径**:Dijkstra算法、Bellman-Ford算法、Floyd算法等,用于寻找两点间最短路径(poj1860, poj3259, poj1062, poj2253, poj1125, poj2240)。 2. **最小生成树**:Prim算法和Kruskal算法,用于构建图的...

    POJ入门题库(含解题思路和答案)

    16. POJ——2703 骑车与走路:可能是一个动态规划或图论问题,解决最短路径或最优决策问题。 17. POJ——2707 求一元二次方程的根:涉及到基础的代数知识,如使用求根公式解决一元二次方程。 18. POJ——2714 求...

    acm新手刷题攻略之poj

    ### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...

    POJ算法题目分类

    图算法是指解决图相关问题的算法,包括图的深度优先遍历和广度优先遍历、最短路径算法、最小生成树算法、拓扑排序、二分图的最大匹配等。 * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指...

    poj图论题目汇总

    #### 2594 *Treasure Exploration - 二分匹配 - **知识点**:二分匹配算法。 #### 2723 Get Luffy Out - 2-SAT - **知识点**:2-SAT问题,一种特殊的布尔满足性问题。 #### 2724 Purifying Machine - 二分匹配 ...

    poj1251 最小生成树

    标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...

    poj:在poj.org上做的一些算法题

    【标题】"poj.org算法题解集合"是关于在poj.org平台上解决的各种算法问题的集合,这个资源主要是为了帮助编程爱好者和学习者提升算法技能。poj.org是一个著名的在线编程竞赛平台,它提供了丰富的算法题目供用户实践...

    POJ2531-Network Saboteur

    【标题】"POJ2531-Network Saboteur" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。该题目属于算法竞赛中的经典问题,旨在考察参赛者的图论知识和编程能力。 【描述】"北大POJ2531-Network ...

    二分图匹配题解1

    求解最小的被吃地鼠数,即求二分图的最大匹配。 5. POJ3041: 这个题目的具体描述不完整,但从题目大意上看,它可能涉及到某种形式的匹配问题,比如工作分配或者任务调度,也可能需要用到二分图最大匹配。 在解决...

Global site tag (gtag.js) - Google Analytics