社区讨论

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

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

讨论操作

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

当前回复
7 条
当前快照
1 份
快照标识符
@mi7yqu02
此快照首次捕获于
2025/11/21 05:48
4 个月前
此快照最后确认于
2025/11/21 05:48
4 个月前
查看原帖
CPP
#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;//点,流量,反向边的位置 
};
vector<sd>G[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
 网络流写法没问题,过了的
*/

回复

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

正在加载回复...