NC236758. 占领城市
描述
输入描述
第一行输入两个整数，分别表示城市数和道路数。
接下来行，每行输入两个整数
，表示从城市
到城市
有一条有向道路连接。保证输入是一个有向无环图，且没有重边和自环。
输出描述
输出一行一个整数，表示Intercept占领所有城市需要的毁灭机器人的最小数目。
示例1
输入:
4 3 3 4 1 3 2 3
输出:
2
C++(g++ 7.5.0) 解法, 执行用时: 106ms, 内存消耗: 1492K, 提交时间: 2022-10-26 18:50:34
#include<bits/stdc++.h>
using namespace std;
const int N=5e2+10;
int rel[N][N],link[N],vis[N];
int n,m;
bool dfs(int x){
for(int i=1;i<=n;i++){
if(!rel[x][i]||vis[i]) continue;
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;
return 1;
}
}
return 0;
}
int main(){
int ans=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
rel[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
cout<<n-ans<<endl;
}
C++ 解法, 执行用时: 73ms, 内存消耗: 1420K, 提交时间: 2022-05-17 16:45:19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,vis[505],link[505],a[505][505];
int dfs(int x)
{
for(int i=1;i<=n;i++)
{
if(!a[x][i]||vis[i]) continue;
vis[i]=1;
if(link[i]==0||dfs(link[i]))
{
link[i]=x;
return 1;
}
}
return 0;
}
void solve()
{
int cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=1;
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) cnt++;
}
printf("%d\n",n-cnt);
}
int main()
{
solve();
return 0;
}