POJ 2594 - Treasure Exploration

一个星球上有很多点,点与点之间有很多单向路

问可重点的最小路径覆盖

利用floyd缩点后求二分图最大匹配

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=;
int m,n;
int map[maxn][maxn];
int link[maxn],vis[maxn];
void floyd()
{
int i,j,k;
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
if(map[i][k]&&map[k][j])
map[i][j]=;
}
}
bool dfs(int t)
{
int i;
for(i=;i<=n;++i)
{
if(!vis[i]&&map[t][i])
{
vis[i]=;
if(link[i]==-||dfs(link[i]))
{
link[i]=t;
return ;
}
}
}
return ;
}
int main()
{
int ans,i,b,a;
while(~scanf("%d%d",&n,&m)&&(n+m))
{
memset(map,,sizeof(map));
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=;
}
floyd();
memset(link,-,sizeof(link));
ans=;
for(i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",n-ans);
}
}
上一篇:☀【CSS3】形状


下一篇:IDEA中创建父子工程与maven打包Springboot聚合工程报错程序包不存在问题处理