用最大流是个假算法（网络流题解：https://blog.csdn.net/qq_43497140/article/details/107302444#comments_12808405），虽然牛客没有重测，我还是来补一发带花树正解（csdn： https://blog.csdn.net/qq_43497140/article/details/107387903）

    首先建图是这样的：

    每个条边拆成两个点x,y,x和y连边

    这条边连的两个点u,v,u拆成d[u]个点，分别和x连边，v拆成d[v]个点，分别和y连边

    然后如果是完全匹配，就输出yes

    解释一下为什么完全匹配就能yes

    如果是完全匹配，每个点都被匹配上了，这样就达到了题目要求的每个点必须连di条边的要求，但是，这是否能保证一条边上两个点，如果一点和该边相连，另一点也同时相连的效果呢？

    当然是可以的，比如对于建图部分所说的点v，他如果匹配到了x，那么要达到完全匹配，y已经不能和x匹配，那必和v（或它拆出来的点）匹配，这样就达到了边上每个点必定同时匹配这条边的效果

 链接：https://ac.nowcoder.com/acm/contest/5666/I
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述

Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices aia_iai and bib_ibi. Find out whether is possible for him to choose some of the edges such that the i-th vertex is incident with exactly did_idi edges.
输入描述:

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m.
The second line contains n integers d1,d2,…,dnd_1, d_2, \dots, d_nd1,d2,…,dn.
The i-th of the following m lines contains two integers aia_iai and bib_ibi.

* 1≤n≤501 \leq n \leq 501≤n≤50
* 1≤m≤1001 \leq m \leq 1001≤m≤100

* 1≤di≤21 \leq d_i \leq 21≤di≤2

* 1≤ai,bi≤n1 \leq a_i, b_i \leq n1≤ai,bi≤n

* ai≠bia_i \neq b_iai=bi
* {ai,bi}≠{aj,bj}\{a_i, b_i\} \neq \{a_j, b_j\}{ai,bi}={aj,bj} for i≠ji \neq ji=j
* The number of tests does not exceed 100.
输出描述:

For each test case, print "`Yes`" without quotes if it is possible. Otherwise, print "`No`" without quotes.

示例1
输入

复制2 1 1 1 1 2 2 1 2 2 1 2 3 2 1 1 2 1 3 2 3

2 1
1 1
1 2
2 1
2 2
1 2
3 2
1 1 2
1 3
2 3

输出

复制Yes No Yes

Yes
No
Yes
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u) for(int i=h[u],v;v=e[i].t,i;i=e[i].n)
const int N=1e3+1,M=1e5+1;
queue<int>q;
int n,m,tot,qwq,ans;
int h[N],lk[N],tag[N],fa[N],pre[N],dfn[N];
struct edge{int t,n;}e[M];
V link(int x,int y){lk[x]=y,lk[y]=x;}
V add_edge(int x,int y){
	if(!lk[x]&&!lk[y])link(x,y),ans++;
	e[++tot]=(edge){y,h[x]},h[x]=tot;
	e[++tot]=(edge){x,h[y]},h[y]=tot;
}
V rev(int x){if(x)rev(x[pre][lk]),link(x,pre[x]);}
I find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
I lca(int x,int y){
	for(qwq++;;x=x[lk][pre],swap(x,y))
		if(dfn[x=find(x)]==qwq)return x;
		else if(x)dfn[x]=qwq;
}
V shrink(int x,int y,int p){
	for(;find(x)!=p;x=pre[y]){
		pre[x]=y,y=lk[x],fa[x]=fa[y]=p;
		if(tag[y]==2)tag[y]=1,q.push(y);
	}
}
I blossom(int u){
	FOR(i,1,n)tag[i]=pre[i]=0,fa[i]=i;
	tag[u]=1,q=queue<int>(),q.push(u);
	for(int p;!q.empty();q.pop())REP(u=q.front())
		if(tag[v]==1)
			p=lca(u,v),shrink(u,v,p),shrink(v,u,p);
		else if(!tag[v]){
			pre[v]=u,tag[v]=2;
			if(!lk[v])return rev(v),1;
			else tag[lk[v]]=1,q.push(lk[v]);
		}
	return 0;
}
vector<int>a[N];
int d[N];
void init()
{
    for(int i=1;i<=N-10;i++) a[i].clear();
    ans=tot=qwq=0;
    memset(h,0,sizeof(h));
    memset(fa,0,sizeof(fa));
    memset(pre,0,sizeof(pre));
    memset(dfn,0,sizeof(dfn));
    memset(lk,0,sizeof(lk));
    memset(tag,0,sizeof(tag));
    memset(d,0,sizeof(d));
}
int main(){
	while(scanf("%d %d",&n,&m)!=EOF)
    {
        init();
 
	for(int x,y;m--;add_edge(x,y))scanf("%d%d",&x,&y);
	FOR(i,1,n)ans+=!lk[i]&&blossom(i);
	cout<<ans<<'\n';
	FOR(i,1,n)cout<<lk[i]<<' ';
    }
}