我是靠谱客的博主 呆萌铅笔,最近开发中收集的这篇文章主要介绍Ural 2038 Minimum Vertex Cover(二分图最小顶点覆盖+快速读入),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意:给你一个二分图,让你把二分图中的点划分为三个集合:一定在最小顶点覆盖集中,一定不在,可能在。


分析:若一个匹配点和一个未匹配点之间有边,那这个匹配点一定在最小顶点覆盖集中,它的另一个匹配点一定不再其中,一个一定不再其中的点连向的所有点都一定给在最小顶点覆盖集中,我们可以就这样DFS一遍求出所有结果。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define MAXN 10005
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n,m,k,ans[3][MAXN],f[MAXN],f2[MAXN];
bool vis[MAXN],jud[3][MAXN];
vector <int> G[MAXN],G2[MAXN];
bool Find(int u)
{
vis[u] = true;
for(int v : G[u])
if(!f[v] || (!vis[f[v]] && Find(f[v])))
{
f[v] = u;
f2[u] = v;
return true;
}
return false;
}
void dfs(int pos,int u,int val)
{
if(jud[pos][u]) return;
jud[pos][u] = true;
ans[pos][u] = val;
if(pos == 1)
{
if(val > 0) dfs(2,f2[u],-1);
else for(int v : G[u]) dfs(2,v,1);
}
else
{
if(val > 0) dfs(1,f[u],-1);
else for(int v : G2[u]) dfs(1,v,1);
}
}
int main()
{
n = read(),m = read(),k = read();
memset(f,0,sizeof(f));
memset(f2,0,sizeof(f2));
for(int i = 1;i <= k;i++)
{
int x,y;
x = read(),y = read();
G[x].push_back(y);
G2[y].push_back(x);
}
for(int i = 1;i <= n;i++)
{
memset(vis,0,sizeof(vis));
Find(i);
}
for(int i = 1;i <= n;i++)
if(!f2[i]) dfs(1,i,-1);
for(int i = 1;i <= m;i++)
if(!f[i]) dfs(2,i,-1);
for(int i = 1;i <= n;i++)
if(ans[1][i] == -1) printf("N");
else
if(ans[1][i] == 0) printf("E");
else printf("A");
printf("n");
for(int i = 1;i <= m;i++)
if(ans[2][i] == -1) printf("N");
else
if(ans[2][i] == 0) printf("E");
else printf("A");
printf("n");
}


最后

以上就是呆萌铅笔为你收集整理的Ural 2038 Minimum Vertex Cover(二分图最小顶点覆盖+快速读入)的全部内容,希望文章能够帮你解决Ural 2038 Minimum Vertex Cover(二分图最小顶点覆盖+快速读入)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(65)

评论列表共有 0 条评论

立即
投稿
返回
顶部