差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:图论_2 [2020/07/16 22:21]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:图论_2 [2021/08/15 16:45] (当前版本)
jxm2001 [一般图最大匹配]
@@ 行 222: / 行 222: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=505,MAXM=1505,Inf=0x7fffffff;
 struct Edge{
@@ 行 555: / 行 508: @@
 };
 </code>
+=== 例题 ===
+[[https://ac.nowcoder.com/acm/contest/5666/H|牛客暑期多校(第一场) H 题]]
+== 题意 ==
+给定一张图，每条边费用已知且容量全部相等。多组询问，每次给定每条边的容量为 $\frac uv$，要求输出从点 $1$ 输送一个单位流量到点
+ $n$ 的最小费用。
+== 题解 ==
+假定每条边为单位流量，计算出每次增广结果并存储，根据费用流算法，必有得到增广路费用递增。
+对每个询问，假设所有边容量乘上 $u$，问题转化为输出从点 $1$ 输送 $v$ 个单位流量到点 $n$ 的最小费用。
+考虑贪心，尽量选择前面的增广路直到流量满足条件，可以考虑二分寻找合适位置。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=55,MAXM=105,Inf=1e9;
+struct Edge{
+	int to,cap,w,next;
+	Edge(int to=0,int cap=0,int w=0,int next=0){
+		this->to=to;
+		this->cap=cap;
+		this->w=w;
+		this->next=next;
+	}
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+int Flow[MAXN],Cost[MAXN],sum[MAXN],flow_cnt;
+void Clear(){mem(head,-1);edge_cnt=0;}//边从0开始编号
+void Insert(int u,int v,int w,int c){
+	edge[edge_cnt]=Edge(v,c,w,head[u]);
+	head[u]=edge_cnt++;
+	edge[edge_cnt]=Edge(u,0,-w,head[v]);
+	head[v]=edge_cnt++;
+}
+struct Dinic{
+	int s,t;
+	int pos[MAXN],dis[MAXN];
+	bool inque[MAXN];
+	bool spfa(){
+		mem(dis,127/3);
+		queue<int>q;
+		q.push(s);
+		inque[s]=true,dis[s]=0,pos[s]=head[s];
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			inque[u]=false;
+			for(int i=head[u];~i;i=edge[i].next){
+				int v=edge[i].to;
+				if(dis[u]+edge[i].w<dis[v]&&edge[i].cap){
+					dis[v]=dis[u]+edge[i].w,pos[v]=head[v];
+					if(!inque[v]){
+						q.push(v);
+						inque[v]=true;
+					}
+				}
+			}
+		}
+		return dis[t]!=dis[0];
+	}
+	int dfs(int u,int max_flow){
+		if(u==t||!max_flow)
+		return max_flow;
+		int flow=0,temp_flow;
+		inque[u]=true;
+		for(int &i=pos[u];~i;i=edge[i].next){
+			int v=edge[i].to;
+			if(!inque[v]&&dis[u]+edge[i].w==dis[v]&&(temp_flow=dfs(v,min(max_flow,edge[i].cap)))){
+				edge[i].cap-=temp_flow;
+				edge[i^1].cap+=temp_flow;
+				flow+=temp_flow;
+				max_flow-=temp_flow;
+				if(!max_flow)
+				break;
+			}
+		}
+		inque[u]=false;
+		return flow;
+	}
+	void MCMF(int s,int t){
+		this->s=s;this->t=t;
+		mem(inque,0);
+		while(spfa()){
+			Flow[++flow_cnt]=dfs(s,Inf);
+			Cost[flow_cnt]=dis[t];
+		}
+	}
+}solver;
+LL gcd(LL a,LL b){
+	while(b){
+		LL t=b;
+		b=a%b;
+		a=t;
+	}
+	return  a;
+}
+int main()
+{
+    int n,m;
+    while(~scanf("%d%d",&n,&m)){
+    	Clear();flow_cnt=0;
+    	int u,v,w;
+    	while(m--){
+    		u=read_int(),v=read_int(),w=read_int();
+    		Insert(u,v,w,1);
+		}
+		solver.MCMF(1,n);
+		_rep(i,1,flow_cnt){
+			sum[i]=sum[i-1]+Cost[i]*Flow[i];
+			Flow[i]+=Flow[i-1];
+		}
+		int q=read_int();
+		while(q--){
+			u=read_int(),v=read_int();
+			if(v>1LL*u*Flow[flow_cnt]){
+				puts("NaN");
+				continue;
+			}
+			int lef=0,rig=flow_cnt,mid,pos;
+			while(lef<=rig){
+				mid=lef+rig>>1;
+				if(v<=1LL*u*Flow[mid]){
+					pos=mid;
+					rig=mid-1;
+				}
+				else
+				lef=mid+1;
+			}
+			LL a=1LL*sum[pos-1]*u+(v-u*Flow[pos-1])*Cost[pos];
+			LL d=gcd(a,v);
+			printf("%lld/%lld\n",a/d,v/d);
+		}
+	}
+    return 0;
+}
+</code>
+</hidden>
 ====  上下界网络流 ====
@@ 行 648: / 行 742: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+c-48;c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+c-48;c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2005,MAXM=2e5+5,Inf=0x7fffffff;
 struct Edge{
@@ 行 873: / 行 920: @@
 时间复杂度 $O(\sqrt nm)$。
-=== 性质 ===
+=== 性质一 ===
-  - 二分图的最小顶点覆盖数等于二分图的最大匹配数
+首先给出二分图的最小顶点覆盖数定义：找到一个最小的点集，使得图中的所有边至少有一点属于该点集。
-  - 二分图的最大独立集数等于节点数减最大匹配数
+二分图的最小顶点覆盖数等于二分图的最大匹配数。
+== 证明 ==
+首先最小顶点覆盖数不小于二分图的最大匹配数，否则无法覆盖匹配边。
+另一方面考虑某个二分图的最大匹配，对所有左部的未配点，跑交替路，同时标记路径上的所有点。
+最后选取所有未标记的左部点和被标记的右部点。
+首先可以知道选取的点一定是已配点。因为所有左部的未配点会被作为起点标记，而右部的未配点一定不会被标记，否则产生增广路。
+然后每条匹配边要么两端点同时被标记，要么两端点同时未被标记，因为只要到达右部已配点，一定会沿已配边到达左部已配点。
+所以所选点数恰好为匹配边数，且已配边一定被覆盖。
+同时不存在某条未配边左部点被标记且右部点未被标记。因为如果该边左端点被标记，则左端点一定会走未配边，固右端点被标记。
+所以选取点构成点覆盖，即最小顶点覆盖数不大于二分图的最大匹配数。证毕。
+=== 性质二 ===
+二分图的最大独立集数等于节点数减最大匹配数。
+==证明==
+首先考虑某个二分图的最大匹配，由于每条匹配边最多有一点存在于独立集，所以二分图的最大独立集数不大于节点数减最大匹配数。
+另一方面，考虑某个二分图的最小点覆盖，取最小点覆盖以外的点构成独立集，则该独立集各点间没有连边，否则说明存在边没有满足点覆盖。
+所以二分图的最大独立集数不小于节点数减最大匹配数。证毕。
 ==== 二分图最大权完美匹配 ====
 === $\text{KM}$ 算法 ===
+== $\text{dfs}$ 版本 ==
 先给出一些概念。
-  * 可行顶标：给那个点一个顶标函数 $l(i)$，满足 $l(u)+l(v)\ge w(u,v)$。
+  * 可行顶标：给那个点一个顶标函数 $l(i)$，满足 $u\in \text{X},v\in \text{Y},l(u)+l(v)\ge w(u,v)$。
-  * 相等子图：只保留原图中 $l(u)+l(v)=w(u,v)$ 的边构成的子图。
+  * 相等子图：只保留原图中 $u\in \text{X},v\in \text{Y},l(u)+l(v)=w(u,v)$ 的边构成的子图。
 容易得到结论：相等子图的完美匹配是原图的最大权完美匹配。
@@ 行 890: / 行 970: @@
 于是算法的重点在于找到合适的顶标函数来构造满足可以完美匹配的相等子图。
+不妨设 $\text{lx}(i)$ 表示左部顶标，$\text{ly}(i)$ 表示右部顶标。
+首先初始化 $\text{lx}(i)$ 为节点 $i$ 连出的最大边权，$\text{ly}(i)$ 为 $0$，该构造满足 $\text{lx}(u)+\text{ly}(v)\ge w(u,v)$。
+考虑依次为左部每个点寻找匹配。
+对左部的某点 $u$，考虑 $\text{dfs}$ 沿着当前相等子图的边寻找增广路，如果可以找到增广路，则该次匹配结束。
+否则将 $\text{dfs}$ 过程中访问的左部点集合记为 $S$，右部点记为 $T$，令 $\overline S=X-S,\overline T=Y-T$。
+考虑向相等子图中加入新边，同时不破坏顶标函数的性质。考虑寻找某个合适的 $a$，将 $S$ 中每个点顶标减小 $a$，$T$ 中每个点顶标增加 $a$。
+本次修改对两端点属于 $S$ 和 $T$ 或 $\overline S$ 和 $\overline T$ 的边无影响。
+对两端点属于 $\overline S$ 和 $T$ 的边 $\text{lx}(u)+\text{ly}(v)$ 值增大，所以仍然满足 $\text{lx}(u)+\text{ly}(v)\ge w(u,v)$。
+对两端点属于 $S$ 和 $\overline T$ 的边，同时由于 $S$ 的顶标减小，更容易加入相等子图中。
+现在考虑 $a$ 的取值，首先 $a$ 必须不小于 $\{\min(\text{lx}(u)+\text{ly}(v)-w(u,v))|u\in S,v\in \overline T\}$。
+否则不能满足 $u\in \text{X},v\in \text{Y},l(u)+l(v)\ge w(u,v)$，破坏了顶标函数的性质。
+同时如果 $a\lt \{\min(\text{lx}(u)+\text{ly}(v)-w(u,v))|u\in S,v\in \overline T\}$，则不会有新边加入。
+所以只能有 $a=\{\min(\text{lx}(u)+\text{ly}(v)-w(u,v))|u\in S,v\in \overline T\}$。
+顶标修改后重复上述过程，直到找到增广路。由于每次修改顶标能保证 $S$ 集合元素至少增加一个，所以最多修改 $O(n)$ 次顶标。
+每次 $\text{dfs}$ 寻找增广路算法时间复杂度 $O(n^2)$，暴力计算 $a$ 时间复杂度 $O(n^2)$。
+所以每个点的匹配复杂度为 $O(n^3)$，总时间复杂度 $O(n^4)$。
+一个优化是动态维护 $lack(v)=\{\min(\text{lx}(u)+\text{ly}(v)-w(u,v))|u\in S\}$，这样计算 $a$ 的时间复杂度优化为 $O(n)$。
+考虑 $\text{dfs}$ 时间复杂度很难跑满 $O(n^2)$，所以算法的平均时间复杂度为 $O(n^3)$。
+<code cpp>
+struct KM{
+	int n,w[MAXN][MAXN],lx[MAXN],ly[MAXN],lack[MAXN];//注意提前把不存在的w设为-Inf
+	int match[MAXN],visx[MAXN],visy[MAXN];
+	bool dfs(int u,int k){
+		visx[u]=k;
+		_rep(v,1,n){
+			if(visy[v]==k)
+			continue;
+			int t=lx[u]+ly[v]-w[u][v];
+			if(!t){
+				visy[v]=k;
+				if(!match[v]||dfs(match[v],k))
+				return	match[v]=u,true;
+			}
+			else
+			lack[v]=min(lack[v],t);
+		}
+		return false;
+	}
+	int get_pair(int n){
+		this->n=n;int k=0;
+		mem(ly,0);mem(match,0);mem(visx,0);mem(visy,0);
+		_rep(i,1,n){
+			lx[i]=-Inf;
+			_rep(j,1,n)
+			lx[i]=max(lx[i],w[i][j]);
+		}
+		_rep(i,1,n){
+			_rep(j,1,n)
+			lack[j]=Inf;
+			while(true){
+				if(dfs(i,++k))
+				break;
+				int a=Inf;
+				_rep(j,1,n){
+					if(visy[j]!=k)
+					a=min(a,lack[j]);
+				}
+				_rep(j,1,n){
+					if(visx[j]==k)
+					lx[j]-=a;
+					if(visy[j]==k)
+					ly[j]+=a;
+					else
+					lack[j]-=a;
+				}
+			}
+		}
+		int ans=0;
+		_rep(i,1,n)
+		ans+=w[match[i]][i];
+		return ans;
+	}
+}
+</code>
+== $\text{bfs}$ 版本 ==
+每次修改顶标新增边后重新 $\text{dfs}$ 将导致代码效率低下。
+考虑将算法过程中的 $\text{dfs}$ 改为 $\text{bfs}$，时间复杂度可优化为 $O(n^3)$。
+<code cpp>
+struct KM{
+	int n,w[MAXN][MAXN],lx[MAXN],ly[MAXN],lack[MAXN],p[MAXN];//注意提前把不存在的w设为-Inf
+	int linkx[MAXN],linky[MAXN],visx[MAXN],visy[MAXN];
+	void augment(int pos){
+		int temp;
+		while(pos){
+			temp=linkx[p[pos]];
+			linkx[p[pos]]=pos;
+			linky[pos]=p[pos];
+			pos=temp;
+		}
+	}
+	void bfs(int s,int k){
+		queue<int>q;
+		_rep(i,1,n)
+		lack[i]=Inf;
+		q.push(s);
+		while(true){
+			while(!q.empty()){
+				int u=q.front();q.pop();
+				visx[u]=k;
+				_rep(v,1,n){
+					if(visy[v]==k)
+					continue;
+					if(lx[u]+ly[v]-w[u][v]<lack[v]){
+						lack[v]=lx[u]+ly[v]-w[u][v];p[v]=u;
+						if(!lack[v]){
+							visy[v]=k;
+							if(!linky[v])
+							return augment(v);
+							else
+							q.push(linky[v]);
+						}
+					}
+				}
+			}
+			int a=Inf;
+			_rep(i,1,n) if(visy[i]!=k)
+			a=min(a,lack[i]);
+			_rep(i,1,n){
+				if(visx[i]==k)lx[i]-=a;
+				if(visy[i]==k)ly[i]+=a;
+				else lack[i]-=a;
+			}
+			_rep(i,1,n){
+				if(visy[i]!=k&&!lack[i]){
+					visy[i]=k;
+					if(!linky[i])
+					return augment(i);
+					else
+					q.push(linky[i]);
+				}
+			}
+		}
+	}
+	int get_pair(int n){
+		this->n=n;int k=0;
+		mem(ly,0);mem(linkx,0);mem(linky,0);mem(visx,0);mem(visy,0);
+		_rep(i,1,n){
+			lx[i]=-Inf;
+			_rep(j,1,n)
+			lx[i]=max(lx[i],w[i][j]);
+		}
+		_rep(i,1,n)
+		bfs(i,i);
+		int ans=0;
+		_rep(i,1,n)
+		ans+=w[linky[i]][i];
+		return ans;
+	}
+}
+</code>
+==== 二分图最大权匹配 ====
+考虑在右部图添加虚点保证右部图点数不小于左部图，然后在每对没有连边的左右部图点间添加权值为 $0$ 的虚边，最后跑 $\text{KM}$ 算法即可。
+==== 二分图最大权最大匹配 ====
+同样考虑在右部图添加虚点保证右部图点数不小于左部图，然后在每对没有连边的左右部图点间添加权值为 $-\inf$ 的虚边，最后跑 $\text{KM}$ 算法即可。
+需要保证答案绝对值一定小于 $\inf$，同时 $n\times \inf$ 不溢出。
+==== 一般图最大匹配 ====
+=== 带花树算法 ===
+把一般图转化为二分图，再套用 $\text{KM}$ 算法解决。而只要消去一般图的所有奇环，就可以将一般图转化为二分图。
+考虑奇环中有 $2k+1$ 个点，最多有 $k$ 条匹配边，所以必然有一个点与其他点间不存在匹配边，而该点可以与奇环外的其他点匹配。
+所以可以考虑先将奇环缩为一个点，并使用并查集维护。
+具体算法仅给出代码和部分注释供参考。
+时间复杂度 $O(n^2log n+nm)$。
+<code cpp>
+struct KM{
+	int n,link[MAXN],pre[MAXN],color[MAXN];
+	int fa[MAXN],cyc_id[MAXN],cyc_cnt;
+	queue<int> q;
+	int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}//寻找花根
+	int LCA(int x,int y){//寻找x,y的总花根
+		++cyc_cnt;
+		x=Find(x),y=Find(y);
+		while(cyc_id[x]!=cyc_cnt){
+			cyc_id[x]=cyc_cnt;//实质上是染色
+			x=Find(pre[link[x]]);//跳到x的上一个花根
+			if(y)swap(x,y);//如果y没有跳到根顶,则切换到y
+		}
+		return x;
+	}
+	void shrink(int x,int y,int p){//将环缩为以p为根的花
+		while(Find(x)!=p){
+			pre[x]=y,y=link[x];//奇环内部没有方向，所以pre需要补充成双向的
+			if(color[y]==2){
+				q.push(y);//现在白点也可以作为出点向外寻找增广路
+				color[y]=1;
+			}
+			if(Find(x)==x)fa[x]=p;//修改花根
+			if(Find(y)==y)fa[y]=p;
+			x=pre[y];
+		}
+	}
+	void update(int x){//从未配白点开始增广
+		int temp;
+		while(x){
+			temp=link[pre[x]];
+			link[x]=pre[x],link[pre[x]]=x;
+			x=temp;
+		}
+	}
+	bool augment(int s){//尝试增广
+		_rep(i,1,n)color[i]=pre[i]=0,fa[i]=i;
+		color[s]=1;
+		while(!q.empty())q.pop();
+		q.push(s);
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				if(color[v]==1){//发现奇环
+					if(Find(u)==Find(v))//已经缩成环了就不必处理
+					continue;
+					int p=LCA(u,v);
+					shrink(u,v,p);shrink(v,u,p);//将通往花根的左右两条路径都修改
+				}
+				else if(!color[v]){
+					pre[v]=u,color[v]=2;
+					if(!link[v]){//找到未配白点
+						update(v);
+						return true;
+					}
+					else{
+						color[link[v]]=1;
+						q.push(link[v]);
+					}
+				}
+			}
+		}
+		return false;
+	}
+	int get_pair(int n){
+		this->n=n;
+		int ans=0;
+		mem(link,0);
+		for(int i=1;i<edge_cnt;i+=2){//预处理加速
+			int u=edge[i].to,v=edge[i+1].to;
+			if(!link[u]&&!link[v])
+			link[u]=v,link[v]=u,ans++;
+		}
+		_rep(i,1,n){
+			if(!link[i]&&augment(i))
+			ans++;
+		}
+		return ans;
+	}
+}
+</code>
+=== 例题 ===
+[[https://ac.nowcoder.com/acm/contest/5666/I|牛客暑期多校(第一场) I 题]]
+== 题意 ==
+给定 $n$ 个点，$m$ 条边，问是否可以选择若干条边，使得每个点度数恰为 $d_i(1\le d_i\le 2)$。
+== 题解 ==
+考虑把度数为 $2$ 的边拆成两个点 $i,i'$，同时将每条边拆成两个点 $e_1,e_2$。
+对原图中的某条边，设两端点为 $u(u'),v(v')$，连边 $u(u')-e_1,e_1-e_2,e_2-v(v')$。
+若新图存在完美匹配则有解，否则无解。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=305,MAXM=500;
+struct Edge{
+	int to,next;
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].next=head[u];
+	edge[edge_cnt].to=v;
+	head[u]=edge_cnt;
+}
+struct KM{
+	int n,link[MAXN],pre[MAXN],color[MAXN];
+	int fa[MAXN],cyc_id[MAXN],cyc_cnt;
+	queue<int> q;
+	int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
+	int LCA(int x,int y){
+		++cyc_cnt;
+		x=Find(x),y=Find(y);
+		while(cyc_id[x]!=cyc_cnt){
+			cyc_id[x]=cyc_cnt;
+			x=Find(pre[link[x]]);
+			if(y)swap(x,y);
+		}
+		return x;
+	}
+	void shrink(int x,int y,int p){
+		while(Find(x)!=p){
+			pre[x]=y,y=link[x];
+			if(color[y]==2){
+				q.push(y);
+				color[y]=1;
+			}
+			if(Find(x)==x)fa[x]=p;
+			if(Find(y)==y)fa[y]=p;
+			x=pre[y];
+		}
+	}
+	void update(int x){
+		int temp;
+		while(x){
+			temp=link[pre[x]];
+			link[x]=pre[x],link[pre[x]]=x;
+			x=temp;
+		}
+	}
+	bool augment(int s){
+		_rep(i,1,n)color[i]=pre[i]=0,fa[i]=i;
+		color[s]=1;
+		while(!q.empty())q.pop();
+		q.push(s);
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				if(color[v]==1){
+					if(Find(u)==Find(v))
+					continue;
+					int p=LCA(u,v);
+					shrink(u,v,p);shrink(v,u,p);
+				}
+				else if(!color[v]){
+					pre[v]=u,color[v]=2;
+					if(!link[v]){
+						update(v);
+						return true;
+					}
+					else{
+						color[link[v]]=1;
+						q.push(link[v]);
+					}
+				}
+			}
+		}
+		return false;
+	}
+	int get_pair(int n){
+		this->n=n;
+		int ans=0;
+		mem(link,0);
+		for(int i=1;i<edge_cnt;i+=2){
+			int u=edge[i].to,v=edge[i+1].to;
+			if(!link[u]&&!link[v])
+			link[u]=v,link[v]=u,ans++;
+		}
+		_rep(i,1,n){
+			if(!link[i]&&augment(i))
+			ans++;
+		}
+		return ans;
+	}
+}solver;
+int deg[MAXN];
+void Add_edge(int u,int v){
+	Insert(u,v);Insert(v,u);
+}
+int main()
+{
+    int n,m;
+    while(~scanf("%d%d",&n,&m)){
+    	mem(head,0);edge_cnt=0;
+    	int sum=0,node_cnt=2*m;
+    	_rep(i,1,n){
+    		deg[i]=read_int();
+    		node_cnt+=deg[i];
+		}
+    	int u,v;
+    	int edge_id=2*n;
+    	while(m--){
+    		u=read_int(),v=read_int();
+    		Add_edge(u,++edge_id);
+    		if(deg[u]>1)
+    		Add_edge(u+n,edge_id);
+    		Add_edge(edge_id,edge_id+1);
+    		Add_edge(++edge_id,v);
+    		if(deg[v]>1)
+    		Add_edge(edge_id,v+n);
+		}
+		if(solver.get_pair(edge_id)*2<node_cnt)
+		puts("No");
+		else
+		puts("Yes");
+	}
+    return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具