社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...