~~去你的萌新~~
by 铃宕 @ 2019-03-15 16:30:06
网络流建边难道不用建反向边吗?
by Wolfycz @ 2019-03-15 16:30:46
@[Wolfycz](/space/show?uid=21633)
然而建了也不行
by 我惠美如画 @ 2019-03-15 16:32:17
@[Wolfycz](/space/show?uid=21633)
大佬帮看下代码呗
by 我惠美如画 @ 2019-03-15 16:39:57
~~用匈牙利吧,几行就完事儿了~~
by YZhe @ 2019-03-15 16:40:14
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
long long m,n,e,head[1000001],cnt,vis[1000001],match[1000001],ans;
struct node
{
int dis,nxt,to;
}ee[1000001];
void add(int from,int to)
{
cnt++;
ee[cnt].to=to;
ee[cnt].nxt=head[from];
head[from]=cnt;
}
bool dfs(int x)
{
for(int i=head[x],y;i;i=ee[x].nxt)
{
if(!vis[y=ee[i].to])
{
vis[y]=1;
if(!match[y]||dfs(match[y]))
{
match[y]=x;return true;
}
}
}
return false;
}
int main()
{
freopen("testdata(1).in","r",stdin);
freopen("testdata(1).out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>e;
int x,y;
for(int i=1;i<=e;i++)
{
cin>>x>>y;
if(y>m||x>n) continue;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
by 方家(rby) @ 2019-03-15 16:41:03
@[方家(rby)](/space/show?uid=146711) 希望更丰富的展现?使用Markdown
by 方家(rby) @ 2019-03-15 16:41:34
```
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
long long m,n,e,head[1000001],cnt,vis[1000001],match[1000001],ans;
struct node
{
int dis,nxt,to;
}ee[1000001];
void add(int from,int to)
{
cnt++;
ee[cnt].to=to;
ee[cnt].nxt=head[from];
head[from]=cnt;
}
bool dfs(int x)
{
for(int i=head[x],y;i;i=ee[x].nxt)
{
if(!vis[y=ee[i].to])
{
vis[y]=1;
if(!match[y]||dfs(match[y]))
{
match[y]=x;return true;
}
}
}
return false;
}
int main()
{
freopen("testdata(1).in","r",stdin);
freopen("testdata(1).out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>e;
int x,y;
for(int i=1;i<=e;i++)
{
cin>>x>>y;
if(y>m||x>n) continue;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
```
by 方家(rby) @ 2019-03-15 16:42:23
@[我惠美如画](/space/show?uid=146702) 你这错误有点多啊……
首先你给super赋值,然后bfs的时候判的是t
建边的时候你的v要写成v+n啊
by Wolfycz @ 2019-03-15 16:46:25
@[Wolfycz](/space/show?uid=21633)
emmmmmmmm最大流代码忘改了0.0
多谢大佬
by 我惠美如画 @ 2019-03-15 16:47:43