https://ac.nowcoder.com/acm/contest/5666/I
hdu3551改版，其实是一样的，从牛逼网友那里学了一手， 据说是claris的带花树板子
一条边会让两个点的度数-1，那么我们就是要去掉一些边，使得每个点去掉du[i]-d[i]个度数
那么就把每个点拆成du[i]-d[i]个，然后对每条边拆成两个点e，e', u的每个点连e，v的每个点连e'，然后跑一般图最大匹配也就是带花树算法，如果完美匹配则为有解
解释一下为什么，如果我们不链接e-e'的话，那么对其实就是每个点拆成的点连上很多边的某一个端点，每一个点和他连的边化作的点的连通块就是一个二分图，搞二分图最大匹配，答案就是拆成的点的个数，因为我们已经满足了du[i]>=d[i]了
然后考虑为什么要把e-e'连起来排一般图最大匹配，因为你二分图最大匹配最后连上的那些边化作的点，每一个连通块不一定会用对应的边，而如果把e-e'连起来，如果某个u-e配对了，e'没有个某个v连起来，那么e'他就落单了，就必不可能是完美匹配
我要评论
#include<bits/stdc++.h>
using namespace std;
const int maxl=1010;
const int N=1010;
int n,m,ans,tot;
int du[maxl],d[maxl],l[maxl],r[maxl],lm[maxl],rm[maxl];
struct edge
{
int u,v;
}ed[maxl];
vector<int> e[maxl];
struct Blossom{
int mate[N],n,ret,nex[N],f[N],mark[N],vis[N],t;
queue<int> Q;
int F(int x){return x==f[x]?x:f[x]=F(f[x]); }
void merge(int x,int y){ f[F(x)]=F(y); }
int lca(int x,int y){
for(t++;;swap(x,y)){
if(~x){
if(vis[x=F(x)]==t) return x; vis[x]=t;
x=mate[x]!=-1?nex[mate[x]]:-1;
}
}
}
void group(int a,int p){
for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){
b=mate[a],c=nex[b];
if(F(c)!=p) nex[c]=b;
if(mark[b]==2) mark[b]=1,Q.push(b);
if(mark[c]==2) mark[c]=1,Q.push(c);
}
}
void aug(int s,const vector<int> G[]){
for(int i=0;i<n;++i)
nex[i]=vis[i]=-1,f[i]=i,mark[i]=0;
while(!Q.empty()) Q.pop();
Q.push(s); mark[s]=1;
while(mate[s]==-1&&!Q.empty()){
int x=Q.front(); Q.pop();
for(int i=0,y;i<(int)G[x].size();++i){
if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){
if(mark[y]==1){
int p=lca(x,y);
if(F(x)!=p) nex[x]=y;
if(F(y)!=p) nex[y]=x;
group(x,p); group(y,p);
}else if(mate[y]==-1){
nex[y]=x;
for(int j=y,k,l;~j;j=l){
k=nex[j]; l=mate[k];
mate[j]=k; mate[k]=j;
}
break;
}else{
nex[y]=x; Q.push(mate[y]);
mark[mate[y]]=1; mark[y]=2;
}
}
}
}
}
bool solve(int _n,const vector<int> G[]){
n=_n; for(int i=0;i<n;++i) mate[i]=-1;
for(int i=t=0;i<n;++i) if(mate[i]==-1) aug(i,G);
for(int i=ret=0;i<n;++i) ret+=mate[i]>i;
return ret*2==n;
}
}blo;
inline void prework()
{
for(int i=1;i<=n;i++)
scanf("%d",&d[i]),du[i]=0;
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
ed[i]=edge{u,v};
++du[u];++du[v];
}
ans=1;tot=0;
for(int i=1;i<=n;i++)
{
if(du[i]<d[i])
{
ans=0;
return;
}
l[i]=tot;r[i]=tot+du[i]-d[i]-1;
tot+=du[i]-d[i];
}
for(int i=1;i<=m;i++)
lm[i]=tot++,rm[i]=tot++;
for(int i=0;i<tot;i++)
e[i].clear();
for(int i=1;i<=m;i++)
{
for(int j=l[ed[i].u];j<=r[ed[i].u];j++)
{
e[j].push_back(lm[i]);
e[lm[i]].push_back(j);
}
e[lm[i]].push_back(rm[i]);
e[rm[i]].push_back(lm[i]);
for(int j=l[ed[i].v];j<=r[ed[i].v];j++)
{
e[j].push_back(rm[i]);
e[rm[i]].push_back(j);
}
}
}
inline void mainwork()
{
if(ans==0)
return;
ans=blo.solve(tot,e);
}
inline void print()
{
if(ans)
puts("Yes");
else
puts("No");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
prework();
mainwork();
print();
}
return 0;
}
本文地址：https://blog.csdn.net/liufengwei1/article/details/107309033
如对本文有疑问， 点击进行留言回复！！
网友评论