差别

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

--- 2020-2021:teams:legal_string:jxm2001:图论_2 [2020/07/17 15:10]
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)$。
-=== 性质 ===
+=== 性质一 ===
-  - 二分图的最小顶点覆盖数等于二分图的最大匹配数
+首先给出二分图的最小顶点覆盖数定义：找到一个最小的点集，使得图中的所有边至少有一点属于该点集。
-  - 二分图的最大独立集数等于节点数减最大匹配数
+二分图的最小顶点覆盖数等于二分图的最大匹配数。
+== 证明 ==
+首先最小顶点覆盖数不小于二分图的最大匹配数，否则无法覆盖匹配边。
+另一方面考虑某个二分图的最大匹配，对所有左部的未配点，跑交替路，同时标记路径上的所有点。
+最后选取所有未标记的左部点和被标记的右部点。
+首先可以知道选取的点一定是已配点。因为所有左部的未配点会被作为起点标记，而右部的未配点一定不会被标记，否则产生增广路。
+然后每条匹配边要么两端点同时被标记，要么两端点同时未被标记，因为只要到达右部已配点，一定会沿已配边到达左部已配点。
+所以所选点数恰好为匹配边数，且已配边一定被覆盖。
+同时不存在某条未配边左部点被标记且右部点未被标记。因为如果该边左端点被标记，则左端点一定会走未配边，固右端点被标记。
+所以选取点构成点覆盖，即最小顶点覆盖数不大于二分图的最大匹配数。证毕。
+=== 性质二 ===
+二分图的最大独立集数等于节点数减最大匹配数。
+==证明==
+首先考虑某个二分图的最大匹配，由于每条匹配边最多有一点存在于独立集，所以二分图的最大独立集数不大于节点数减最大匹配数。
+另一方面，考虑某个二分图的最小点覆盖，取最小点覆盖以外的点构成独立集，则该独立集各点间没有连边，否则说明存在边没有满足点覆盖。
+所以二分图的最大独立集数不小于节点数减最大匹配数。证毕。
 ==== 二分图最大权完美匹配 ====
@@ 行 1079: / 行 1157: @@
 === 带花树算法 ===
+把一般图转化为二分图，再套用 $\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

用户工具

站点工具

差别

页面工具