MYF

POJ 1422 Air Raid

Posted on | In | | Visitors

题目链接

POJ 1422

方法：二分图找最小路径覆盖

题目分析

题目大意

一个镇里所有的路都是单向路且不会组成回路。派一些伞兵去那个镇里，要到达所有的路口，有一些或者没有伞兵可以不去那些路口，只要其他人能完成这个任务。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

解析

二分图的题目。

由输入可以知道该城市中的通路数量，那么如果派出最少的伞兵，必然是从每条路可以到达的最起始位置（这词说的好奇怪。。。但是就是这个意思）到最末尾位置，这样才能走最少的路径，然后题目就转化为了找最小路径覆盖。

根据公式，我们知道这样一个结论：

最小路径覆盖 ＝ 顶点数 - 最大匹配数

所以这道题就转化为了找最大匹配数的问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(checker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=300+10;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int mp[maxn][maxn]={},flag[maxn]={},check[maxn];
int p,n;
int dfs(int u){
    for (int v=1; v<=n; v++)
        if (mp[u][v]&&!flag[v]) {
            flag[v]=1;
            if (check[v]==-1 ||dfs(check[v])) {
                check[v]=u;
                return 1;
            }
        }
    return 0;
}
int hungary(){
    memset(check,-1,sizeof(check));
    int rt=0;
    for (int u=1; u<=n; u++) {
        memset(flag,0,sizeof(flag));
        rt+=dfs(u);
    }
    return rt;
}
int main(){
    int t,tmp,x,y;
    scanf("%d",&t);
    while (t--) {
        Memset(mp, 0);
        scanf("%d%d",&n,&p);
        for (int i=1; i<=p; i++) {
            scanf("%d%d",&x,&y);
            mp[x][y]=1;
        }
        cout<<n-hungary()<<endl;
    }
}