`

hdu 1151 Air Raid(最小路径覆盖)

阅读更多

Air Raid

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1313    Accepted Submission(s): 831

Problem 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 intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.
 
Input
Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct.
 
Output
The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.
Sample Input
2 4 3 3 4 1 3 2 3 3 3 1 3 1 2 2 3
Sample Output
2 1
           典型的最小路径覆盖!最小路径覆盖 == 顶点数 - 最大匹配数
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;

const int N = 125;

int pre[N];
bool flag[N];
vector<int> map[N];
int n;

int find(int cur)
{
    int i, k;
    for(i = 0; i < map[cur].size(); i++)
    {
        k = map[cur][i];
        if(!flag[k])
        {
            flag[k] = true;
            if(pre[k] == -1 || find(pre[k]))
            {
                pre[k] = cur;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i, t, s, e, num, sum;
    scanf("%d", &t);
    while(t--)
    {
        memset(pre, -1, sizeof(pre));
        for(i = 1; i <= n; i++) map[i].clear();
        scanf("%d", &n);
        scanf("%d", &num);
        for(i = 1; i <= num; i++)
        {
            scanf("%d %d", &s, &e);
            map[s].push_back(e);
        }
        sum = 0;
        for(i = 1; i <= n; i++)
        {
            memset(flag, false, sizeof(flag));
            sum += find(i);
        }
        printf("%d\n", n - sum);
    }

    return 0;
}
 
0
2
分享到:
评论

相关推荐

    最小园覆盖

    hdu2215 最简单的最小圆覆盖

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    二分匹配题集

    3. **Air Raid (HDU 1179)** - **知识点**:最小路径覆盖问题,同样可以通过转换成最大匹配问题来解决。 - **解题思路**:构建二分图模型,利用最大匹配算法找到最大匹配,再利用Konig定理来求最小路径覆盖。 4....

    HDU题目java实现

    8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU图论题目分类

    本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU acm-PPT课件

    对于特定问题,比如最大子序列和、最小覆盖子集等,需要掌握特定算法,如Kadane's algorithm或Dijkstra's algorithm。 四、数学基础:开启解题新维度 数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程...

    ACM HDU

    1. **基础算法**:包括排序(快速排序、归并排序等)、搜索(二分查找、深度优先搜索等)、图论(最短路径、最小生成树等)。 2. **动态规划**:解决许多具有重叠子问题和最优子结构的问题,如背包问题、最长公共子...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    Hdu1000—2169部分代码

    4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。 6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等...

    杭电ACMhdu1163

    4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论(模运算、最大公约数、最小公倍数)、组合数学(排列组合、容斥原理)、概率论等。 5. **贪心策略**:部分题目可以通过贪心算法求解,即每次做出...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU最全ac代码

    1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小生成树、拓扑排序等)和动态规划等。 2. **数据结构**:如链表、...

    hdu2101解决方案

    hdu2101AC代码

Global site tag (gtag.js) - Google Analytics