社区讨论

求助90分,我注释里面的数据过不了,建图有错吗?

P3386【模板】二分图最大匹配参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi7yqtrz
此快照首次捕获于
2025/11/21 05:48
4 个月前
此快照最后确认于
2025/11/21 05:48
4 个月前
查看原帖
#include<bits/stdc++.h> #define N 100005 using namespace std; const int INF=0x7fffffff; int n,m,a,b; bool vis[N]; struct sd { int to,cap,rev;//点,流量,反向边的位置 }; vectorG[N]; void add(int a,int b,int c) { G[a].push_back((sd){b,c,G[b].size()}); G[b].push_back((sd){a,0,G[a].size()-1});//反向边要权为0 } int dfs(int now,int t,int f) { if(now==t) return f; vis[now]=true; for(int i=G[now].size()-1;i>=0;i--){ sd &tmp=G[now][i]; if(!vis[tmp.to] && tmp.cap>0) { int d=dfs(tmp.to,t,min(f,tmp.cap)); if(d>0) { tmp.cap-=d; G[tmp.to][tmp.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; while(1) { memset(vis,0,sizeof(vis)); int f=dfs(s,t,INF);//增广路 if(f==0) return flow; flow+=f; } } int main() { scanf("%d%d%d",&a,&b,&m); n=a+b+2; for(int i=1;i<=a;i++) {add(1,i+1,1);add(i+1,1,1);} for(int i=1;i<=m;i++) { int u,v;//连已有的边 scanf("%d%d",&u,&v); if(u<=a && v<=b) add(u+1,v+a+1,1), add(v+a+1,u+1,1); } for(int i=1;i<=b;i++) {add(i+a+1,n,1);add(n,i+a+1,1);} int ans=max_flow(1,n); printf("%d\n",ans); } /* 5 5 11 1 2 1 5 2 2 2 3 2 4 3 1 3 5 4 1 4 2 4 5 5 2 (我改一改交网络流是A了的,并没有写错熬) */

回复

1 条回复,欢迎继续交流。

正在加载回复...