匈牙利算法, 常数小,复杂度没有网络流优秀,但是其实小数据跑的更快
#include<bits/stdc++.h> using namespace std; const int maxn=2e3+5; int n,m,k; vector<int>e[maxn]; int match[maxn],vis[maxn]; bool dfs(int u){ int len=e[u].size(); for(int i=0;i<len;i++){ int v=e[u][i]; if(vis[v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; match[u]=v; return true; } } return false; } int xyl(){ int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } return ans; } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=k;i++){ int a,b; scanf("%d%d",&a,&b); if(a>n||b>m)continue; e[a].push_back(n+b); e[n+b].push_back(a); } printf("%d",xyl()); return 0; }裸的匈牙利,因为自带记录匹配,直接输出即可
#include <cstdio> #include <cstring> using namespace std; const int maxn=2e3+5; int n,m,k; int e[maxn][maxn]; int match[maxn],vis[maxn]; bool dfs(int u){ for(int v=m+1;v<=n;v++){ if(vis[v]||!e[u][v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){// 如果v没有匹配,或者v的匹配找到了新的匹配 match[v]=u; match[u]=v; // 更新匹配信息 return true; } } return false; } int xyl(){ int ans=0; memset(match,0,sizeof(match)); for(int i=1;i<=n;i++){// 对每一个点尝试匹配 memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } return ans; } inline void init(){ memset(e,0,sizeof(e)); } int main(){ scanf("%d%d",&m,&n); int u,v; while(scanf("%d%d",&u,&v)){ if(u==-1&&v==-1)break; e[u][v]=1; e[v][u]=1; } printf("%d\n",xyl()); for(int i=1;i<=m;i++){ if(match[i]){ printf("%d %d\n",i,match[i]); } } return 0; }行列匹配数是否==行数,可以只考虑一种移法,只移动行或者列,然后只要每个行列匹配成功,更换他们的位置并不会影响匹配数
#include<bits/stdc++.h> using namespace std; const int maxn=205; int n,m,k; int e[maxn][maxn]; int match[maxn],vis[maxn],a[maxn][maxn]; bool dfs(int u){ for(int v=1;v<=n;v++){ if(vis[v]||!e[u][v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; return true; } } return false; } int xyl(){ int ans=0; memset(match,0,sizeof match); for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i))ans++; } return ans; } inline void init(){ memset(e,0,sizeof e); } int main(){ int tt; cin>>tt; while(tt--){ cin>>n; init(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&e[i][j]); } } int ans=xyl(); if(ans==n)printf("Yes\n"); else printf("No\n"); } }裸的KM
#include<bits/stdc++.h> using namespace std; #define int long long const long long maxn=1005,inf=9e18; int n,m,mp[maxn][maxn],matched[maxn],p[105][105],q[105][105]; int slack[maxn],ex[maxn],ey[maxn],pre[maxn]; int visx[maxn],visy[maxn]; void match(int u){ int x,y=0,yy=0,d; memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++)slack[i]=inf; matched[y]=u; while(1){ x=matched[y]; d=inf; visy[y]=1; for(int i=1;i<=n;i++){ if(visy[i])continue; if(slack[i]>ex[x]+ey[i]-mp[x][i]){ slack[i]=ex[x]+ey[i]-mp[x][i]; pre[i]=y; } if(slack[i]<d){ d=slack[i]; yy=i; } } for(int i=0;i<=n;i++){ if(visy[i])ex[matched[i]]-=d,ey[i]+=d; else slack[i]-=d; } y=yy; if(matched[y]==-1)break; } while(y){ matched[y]=matched[pre[y]]; y=pre[y]; } } int km(){ memset(matched,-1,sizeof(matched)); memset(ex,0,sizeof(ex)); memset(ey,0,sizeof(ey)); for(int i=1;i<=n;i++){ memset(visy,0,sizeof(visy)); match(i); } int ans=0; for(int i=1;i<=n;i++){ if(matched[i]!=-1)ans+=mp[matched[i]][i]; } return ans; } signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=-inf; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>p[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>q[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ mp[i][j]=p[i][j]*q[j][i]; } } // for(int i=1;i<=m;i++) // { // int u,v,w; // scanf("%lld%lld%lld",&u,&v,&w); // mp[u][v]=w; // } printf("%lld\n",km()); for(int i=1;i<=n;i++){ // printf("%lld ",matched[i]); } return 0; }分析一下AB国的情况: A国只能一奇一偶,所以这个国的团中最多只有1个或者2个人
B国奇偶相同的在同一个团
所以可以枚举a国的每一个团,1或者2,跟b国进行匹配
最大团=补图最大独立集=总点数 − - −补图最大匹配数
不能无脑memset而要用时间戳进行优化匈牙利,否则会T
(最后这题写着多组输入但是其实并没有,数据有锅)
#include<bits/stdc++.h> using namespace std; const int maxn=3005; int n,m,k,cnt,ans,num,t,flag[maxn]; int e[maxn][maxn],head[maxn],a[maxn],b[maxn]; int match[maxn],vis[maxn]; struct edge{ int v,nex; }ee[2000*2000+5]; inline void add(int u,int v){ ee[++cnt].v=v; ee[cnt].nex=head[u]; head[u]=cnt; } bool dfs(int u){ for(int i=head[u];i;i=ee[i].nex){ int v=ee[i].v; if(vis[v]!=num&&flag[v]==t){ vis[v]=num; if(!match[v]||dfs(match[v])){ match[v]=u; return true; } } } return false; } int main(){ int tt,A,B; cin>>tt; while(tt--){ ans=0; cin>>A>>B>>m; for(int i=1;i<=A;i++){ scanf("%d",&a[i]); } for(int i=1;i<=B;i++){ scanf("%d",&b[i]); } for(int i=1;i<=B;i++){ if(b[i]&1){ for(int j=1;j<=B;j++){ if(!(b[j]&1)&&!((__builtin_popcount((b[i]|b[j])))&1)){ add(i,j); } } } } int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); e[u][v+A]=1; e[v+A][u]=1; } for(int i=1;i<=B;i++){ if((b[i]&1)){ num++; if(dfs(i))ans++; } } ans=B-ans; for(int i=1;i<=A;i++){ t++; int sum=0,now=0; memset(match,0,sizeof match); for(int j=1;j<=B;j++){ if(e[i][j+A]){ flag[j]=t; now++; } } for(int j=1;j<=B;j++){ if(flag[j]==t&&(b[j]&1)){ num++; if(dfs(j))sum++; } } ans=max(ans,now-sum+1); } for(int i=1;i<=A;i++){ for(int j=i+1;j<=A;j++){ if((a[i]^a[j])&1){ t++; int sum=0,now=0; memset(match,0,sizeof match); for(int k=1;k<=B;k++){ if(e[i][A+k]&&e[j][A+k]){ flag[k]=t; now++; } } for(int k=1;k<=B;k++){ if(flag[k]==t&&(b[k]&1)){ num++; if(dfs(k))sum++; } } ans=max(ans,now-sum+2); } } } cout<<ans<<endl; } return 0; }给定有向图 G = ( V , E ) G=(V,E) G=(V,E) 。设 P P P 是 G G G 的一个简单路(顶点不相交)的集合。如果 V V V 中每个定点恰好在 P P P的一条路上,则称 P P P 是 G G G 的一个路径覆盖。 P P P中路径可以从 V V V 的任何一个定点开始,长度也是任意的,特别地,可以为 0 0 0 。 G G G 的最小路径覆盖是 G G G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) G G G 的最小路径覆盖。
提示:设 V = { 1 , 2 , . . . , n } V=\{1,2,...,n\} V={1,2,...,n} ,构造网络 G 1 = { V 1 , E 1 } G_1=\{V_1,E_1\} G1={V1,E1} 如下:
V 1 = { x 0 , x 1 , . . . , x n } ∪ { y 0 , y 1 , . . . , y n } V_1=\{x_0,x_1,...,x_n\}\cup\{y_0,y_1,...,y_n\} V1={x0,x1,...,xn}∪{y0,y1,...,yn}
E 1 = { ( x 0 , x i ) : i ∈ V } ∪ { ( y i , y 0 ) : i ∈ V } ∪ { ( x i , y j ) : ( i , j ) ∈ E } E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\} E1={(x0,xi):i∈V}∪{(yi,y0):i∈V}∪{(xi,yj):(i,j)∈E}
每条边的容量均为 1 1 1 ,求网络 G 1 G_1 G1 的 ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 最大流。
题目直接给出了提示,可是我太蒻了没有看懂…
原图是这样子的: 要我们求最小覆盖路径,我们可以先把图看成没有边,此时覆盖路径数为11,通过手玩可以发现,每当我们连上一条边之后,这个路径数就会减少1,而每一条路径上,一个点只能被另外一个点连上,这就符合匹配的原理,我们由此构建出二分图: 可以看出最小路径覆盖数=总点数-最大流,因为最大流即为匹配数,被匹配上的点就不需要做出发点
题目要求我们输出路径,在dfs找增广路的时候记录下每一个点 u − > v u->v u−>v的 v v v就好
#include<bits/stdc++.h> using namespace std; const int inf =0x3f3f3f3f,maxn=1e5+5,maxm=4e5+5; int cur[maxn],head[maxn],dep[maxn],to[maxn],flag[maxn]; int cnt=1,n,m,s,t; struct edge{ int v,w,nex; }e[maxm*2]; inline void add_edge(int u,int v,int w){ e[++cnt].v=v; e[cnt].w=w; e[cnt].nex=head[u]; head[u]=cnt; e[++cnt].v=u; e[cnt].w=0; e[cnt].nex=head[v]; head[v]=cnt; } bool bfs(){ memset(dep,0,sizeof(dep)); for(int i=0;i<=2*n+5;i++){//如果要拆点或者其他的一定记得把范围开大点!!! cur[i]=head[i]; } dep[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nex){ int v=e[i].v; if(!dep[v]&&e[i].w){ dep[v]=dep[u]+1; q.push(v); if(v==t)return true; } } } return false; } int dfs(int u,int now){ if(u==t||now==0){ return now; } int flow=0,rlow=0; for(int i=cur[u];i;i=e[i].nex){ int v=e[i].v; if(e[i].w&&dep[v]==dep[u]+1){ if(rlow=dfs(v,min(now,e[i].w))){ flow+=rlow; now-=rlow; e[i].w-=rlow; e[i^1].w+=rlow; to[u]=v; if(u!=s)flag[v-n]=1; if(now==0)return flow; } } } if(!flow)dep[u]=-1; return flow; } int dinic(){ int maxflow=0; while(bfs()){ maxflow+=dfs(s,inf); } return maxflow; } int main(){ scanf("%d%d",&n,&m); int u,v,w; s=0,t=2*n+1; for(int i=1;i<=n;i++){ add_edge(s,s+i,1); add_edge(s+n+i,t,1); } for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); add_edge(s+u,s+n+v,1); } int ans=dinic(); for(int i=1;i<=n;i++){ if(!flag[i]){ int now=i; printf("%d ",now); while(to[now]&&to[now]!=t){ printf("%d ",to[now]-n); now=to[now]-n; } cout<<endl; } } printf("%d",n-ans); return 0; }每隔一个墙就 c n t + + cnt++ cnt++,对行列进行匹配求出最大匹配数即可
#include<bits/stdc++.h> using namespace std; const int maxn=2005+5; int xcnt=1,ycnt=1; int n,m,k; int e[maxn][maxn],x[maxn][maxn],y[maxn][maxn]; int match[maxn],vis[maxn]; char a[maxn][maxn]; bool dfs(int u){ for(int v=1;v<=xcnt;v++){ if(vis[v]||!e[u][v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; return true; } } return false; } int xyl(){ int ans=0; memset(match,0,sizeof match); for(int i=1;i<=xcnt;i++){ memset(vis,0,sizeof vis); if(dfs(i))ans++; } return ans; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='*'){ x[i][j]=xcnt; } else if(a[i][j]=='#')xcnt++; } xcnt++; } for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ if(a[i][j]=='*'){ y[i][j]=ycnt; } else if(a[i][j]=='#')ycnt++; } ycnt++; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int u=x[i][j]; int v=y[i][j]; if(a[i][j]=='*'){ e[u][v]=1; } } } printf("%d",xyl()); return 0; }刚开始读错了题,后面突然发现是要求最大团,秒杀之
再写一遍:最大团=补图最大独立集=总点数-补图最大匹配数
#include<bits/stdc++.h> using namespace std; const int maxn=1005; int n,m,k,xcnt,ycnt; int e[maxn][maxn]; int match[maxn],vis[maxn],a[maxn][maxn]; struct xd{ int x,y1,y2; }xd[maxn]; struct yd{ int x1,x2,y; }yd[maxn]; bool dfs(int u){ for(int v=1;v<=n;v++){ if(vis[v]||!e[u][v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; return true; } } return false; } int xyl(){ int ans=0; memset(match,0,sizeof match); for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i))ans++; } return ans; } int main(){ cin>>n; int x1,x2,y1,y2; for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1==x2){ xd[++xcnt].x=x1; xd[xcnt].y1=y1; xd[xcnt].y2=y2; } else if(y1==y2){ yd[++ycnt].y=y1; yd[ycnt].x1=x1; yd[ycnt].x2=x2; } } for(int i=1;i<=xcnt;i++){ int x=xd[i].x; int y1=xd[i].y1; int y2=xd[i].y2; if(y1>y2)swap(y1,y2); for(int j=1;j<=ycnt;j++){ int y=yd[j].y; int x1=yd[j].x1; int x2=yd[j].x2; if(x1>x2)swap(x1,x2); if(x1<=x&&x2>=x&&y1<=y&&y2>=y){ e[i][j]=1; } // e[i][j]=1; } } printf("%d",max(xcnt,max(ycnt,n-xyl()))); return 0; }这个题做的我晚上脑子快要爆炸…
一看数据范围很明显是要 n l o g n nlogn nlogn的做法才行
半天也没看明白题目的真意…
题目给出了反图
题目问加上哪些边可以让最大团变大
而 最大团=总点数-补图最大匹配数
所以补图的最大匹配数越小,最大团就越大,也就是补图最大独立集越大,也就是删掉哪些边能让图的最大独立集增大
luogu上的dalao的分析: 考虑如下定理:若一条边一定在最大匹配中,则在最终的残量网络中,这条边一定满流,且这条边的两个顶点一定不在同一个强连通分量中。
证明也很简单:首先满流的要求是很显然的,其次,如果这两个点在同一个强连通分量中,那么一定有一个环经过这条边,沿着环增广一下,网络仍然满足流量限制,但是这条边就不满流了,于是就得到了一组新的最大匹配。
于是我们终于读懂题目了,就是求二分图匹配的必须边
直接在残量网络里跑 t a r j a n tarjan tarjan,就是如果这条边没有满流就连上
对于一条边 ( x , y ) (x,y) (x,y)
如果 ( x , y ) (x,y) (x,y)是一条匹配边或者 x x x, y y y在同一个强联通分量里,那么这就是一条最大匹配的可行边
如果 ( x , y ) (x,y) (x,y)是一条匹配边并且 x x x, y y y不在同一个强连通分量里,那么这就是一条必须边
#include<bits/stdc++.h> using namespace std; const int maxn=2e4+5; const int maxm=150000+5,inf=0x3f3f3f3f; int head[maxn],n,m,cnt=1,dep[maxn],vis[maxn],cur[maxn]; int s,t,co[maxn]; struct edge{ int v,w,nex; }e[maxm*2]; vector<int>ee[maxn]; inline void add_edge(int u,int v,int w){ e[++cnt].v=v; e[cnt].w=w; e[cnt].nex=head[u]; head[u]=cnt; e[++cnt].v=u; e[cnt].w=0; e[cnt].nex=head[v]; head[v]=cnt; } bool bfs(){ memset(dep,0,sizeof(dep)); for(int i=s;i<=t;i++){//如果要拆点或者其他的一定记得把范围开大点!!! cur[i]=head[i]; } dep[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nex){ int v=e[i].v; if(!dep[v]&&e[i].w){ dep[v]=dep[u]+1; q.push(v); if(v==t)return true; } } } return false; } int dfs(int u,int now){ if(u==t||now==0){ return now; } int flow=0,rlow=0; for(int i=cur[u];i;i=e[i].nex){ int v=e[i].v; if(e[i].w&&dep[v]==dep[u]+1){ if(rlow=dfs(v,min(now,e[i].w))){ flow+=rlow; now-=rlow; e[i].w-=rlow; e[i^1].w+=rlow; if(now==0)return flow; } } } if(!flow)dep[u]=-1; return flow; } int dinic(){ int maxflow=0; while(bfs()){ maxflow+=dfs(s,inf); } return maxflow; } namespace Tarjan { std::vector<int> v[maxn]; int dfn[maxn],low[maxn],col[maxn],st[maxn],f[maxn]; int top,p,cnt,mid,tot; std::pair<int,int> ans[150005]; void tarjan(int x) { dfn[x]=low[x]=++cnt; f[x]=1,st[++top]=x; for(int i=0;i<v[x].size();++i) { int j=v[x][i]; if(!dfn[j]) tarjan(j),low[x]=min(low[x],low[j]); else if(f[j]) low[x]=min(low[x],dfn[j]); } if(dfn[x]==low[x]) { ++p; do { mid=st[top--]; f[mid]=0; col[mid]=p; }while(mid!=x); } } void solve() { for(int i=s;i<=t;i++) for(int j=head[i];j;j=e[j].nex) if(e[j].w) v[i].push_back(e[j].v); for(int i=s;i<=t;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) { if(co[i]) continue; for(int j=head[i];j;j=e[j].nex) if(col[i]!=col[e[j].v]&&!e[j].w&&e[j].v!=s) { int xx=min(i,e[j].v); int yy=max(i,e[j].v); ans[++tot]=make_pair(xx,yy); } } std::sort(ans+1,ans+tot+1); printf("%d\n",tot); for(int i=1;i<=tot;i++) printf("%d %d\n",ans[i].first,ans[i].second); } } void rs(int u,int c){ co[u]=c; for(int i=0;i<ee[u].size();i++) { int v=ee[u][i]; if(co[v]!=2) continue; rs(v,c^1); } } int main(){ cin>>n>>m; int x,y; t=n+1; s=0; for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); ee[x].push_back(y); ee[y].push_back(x); } for(int i=1;i<=n;i++){ co[i]=2; } for(int i=1;i<=n;i++){ if(co[i]==2)rs(i,0); } for(int i=1;i<=n;i++){ if(!co[i])add_edge(s,i,1); else add_edge(i,t,1); } for(int i=1;i<=n;i++){ if(co[i])continue; for(int j=0;j<ee[i].size();j++){ add_edge(i,ee[i][j],1); } } int an=dinic(); Tarjan::solve(); return 0; }正负KM
#include<bits/stdc++.h> using namespace std; #define int long long const long long maxn=1005,inf=1e18; int n,m,mp[maxn][maxn],matched[maxn]; int slack[maxn],ex[maxn],ey[maxn],pre[maxn]; int visx[maxn],visy[maxn]; inline void init(){ memset(slack,0,sizeof slack); memset(ex,0,sizeof ex); memset(ey,0,sizeof ey); memset(pre,0,sizeof pre); memset(matched,0,sizeof matched); memset(visx,0,sizeof visx); memset(visy,0,sizeof visy); } void match(int u){ int x,y=0,yy=0,d; memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++)slack[i]=inf; matched[y]=u; while(1){ x=matched[y]; d=inf; visy[y]=1; for(int i=1;i<=n;i++){ if(visy[i])continue; if(slack[i]>ex[x]+ey[i]-mp[x][i]){ slack[i]=ex[x]+ey[i]-mp[x][i]; pre[i]=y; } if(slack[i]<d){ d=slack[i]; yy=i; } } for(int i=0;i<=n;i++){ if(visy[i])ex[matched[i]]-=d,ey[i]+=d; else slack[i]-=d; } y=yy; if(matched[y]==-1)break; } while(y){ matched[y]=matched[pre[y]]; y=pre[y]; } } int km(){ memset(matched,-1,sizeof(matched)); memset(ex,0,sizeof(ex)); memset(ey,0,sizeof(ey)); for(int i=1;i<=n;i++){ memset(visy,0,sizeof(visy)); match(i); } int ans=0; for(int i=1;i<=n;i++){ if(matched[i]!=-1)ans+=mp[matched[i]][i]; } return ans; } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=-inf; // for(int i=1;i<=m;i++){ // int u,v,w; // scanf("%lld%lld%lld",&u,&v,&w); // mp[u][v]=w; // } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%lld",&mp[i][j]); } } int mm=km(); init(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ mp[i][j]=-mp[i][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]==-inf)mp[i][j]=inf; printf("%lld\n%lld",-km(),mm); return 0; }黑题,咕咕咕待补