主要是做题时感觉思路很混乱,写篇博客清醒清醒
参考文献
一位大佬的远古博客 (最小点覆盖的证明),配合算阶食用更佳
思路
因为要用最少的点将所有的边覆盖(就是求最小点覆盖)
C++ 代码
#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
char c;bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
const int maxn=300;
int n,m,k,f[maxn],hd[maxn],vis[maxn];
struct node{
int to,nt;
}e[maxn*maxn];
inline void add(int x,int y){e[++k].to=y;e[k].nt=hd[x];hd[x]=k;}
inline bool vivi(int x)//二分图
{
for(int i=hd[x];i;i=e[i].nt)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=1;
if(!f[v]||(vivi(f[v])))
{
f[v]=x;
re 1;
}
}
}
re 0;
}
int main()
{
freopen("in.txt","r",stdin);
int x,y,z,K;
while(2333)
{
rd(n);
if(!n)re 0;
rd(m),rd(K);
memset(f,0,sizeof f);
memset(hd,0,sizeof hd);
inc(i,1,K)
{
rd(z),rd(x),rd(y);
if(!x||(!y))continue;//起始点是0(不用覆盖)
add(x,y);
}
int ans=0;
inc(i,1,n)
{
memset(vis,0,sizeof vis);
if(vivi(i))++ans; //累加匹配数
}
printf("%d\n",ans);
}
re 0;
}
blablabla
大佬,为什么”起始点是0,不用覆盖”啊
我是弱智,加粗的字被忽略了