本文主要是介绍排雷，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
排雷
问题描述
一队士兵在巡逻时发现在他们的一条必经之路上被埋上了地雷。工兵发现，地雷埋在公路的左右两侧，而且公路两侧的一些地雷有细线相连，只要拆除一颗地雷，公路另一边跟它通过细线相连的所有地雷就会爆炸。
工兵还发现地雷具有这些特点：一个地雷爆炸不会影响跟它相连的地雷。两个雷之间可能有多条细线相连。细线只连接位于公路两侧的地雷，同一侧的地雷没有细线相连。
为了避免公路被炸毁，工兵想拆掉尽可能多的地雷，问：工兵最多可拆掉多少地雷？
输入格式
第一行包括三个整数N1,N2和M，分别表示左侧地雷数，右侧地雷数和细线总数。（左右两边的地雷分别按1…N1和1…N2标号）
接下来有M行，每行有两个整数A，B（1<=A<=N1,1<=B<=N2），表示左边的地雷A和右边的地雷B有一条细线相连。
输出格式
一整数表示能拆掉的最大地雷数
样例输入
3 3 5
1 2
2 1
2 2
2 3
3 2
样例输出
4
提示
工军拆掉了左侧的1、3和右侧的1、3号地雷。
100%的数据 V<=1000 0<=N1,N2<=500 M<=250,000
思路
跑一遍最大匹配，总数减去结果就是答案
#include<bits/stdc++.h>
using namespace std;
int ans=0,n,m,z,s;
const int cross=505;//防伪标志
bool maps[cross][cross];
bool road[cross];
int link[cross];
bool findit(int v){int i;for(i=1;i<=m;i++){if(maps[v][i]&&(!road[i])){road[i]=true;if(link[i]==0||findit(link[i])){link[i]=v;return true;}}}return false;
}
int main(){scanf("%d%d%d",&n,&m,&z);int a,b;for(int i = 1;i<=z;i++){scanf("%d%d",&a,&b);maps[a][b]=1;}for(int i=1;i<=n;i++){for(int j =1;j<=m;j++)road[j]=false;if(findit(i))ans++;}printf("%d",m+n-ans);return 0;
}
这篇关于排雷的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
