求助
查看原帖
求助
429102
cflsfzh楼主2025/6/18 08:10

好久没打网络流了,为什么 T 成10分了?

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fs first
#define sc second
#define il inline
#define re register
using namespace std;
il int read()
{
	re int x=0;
	re int ff=1;
	re char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')
			ff=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*ff; 
}
const int N=1006;
const int M=5e4+6;
struct edge{
	int v,next,w;
};
edge e[M<<2];
int s,t,m,k=1,head[N],d[N],cur[N];
void add(int u,int v,int w)
{
	e[++k].v=v;
	e[k].w=w;
	e[k].next=head[u];
	head[u]=k;
	return;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	memcpy(cur,head,sizeof(cur));
	queue<int> q;
	q.push(0);
	d[0]=1;
	while(!q.empty()){
		int u=q.front();
		if(u==s+t+1)
			return 1;
		q.pop();
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v;
			if(e[i].w&&!d[v])
				q.push(v),d[v]=d[u]+1; 
		}
	}
	return 0;
}
int dfs(int u,int z)
{
	if(u==s+t+1)
		return z;
	int awa=0;
	for(int i=cur[u];i&&z;i=e[i].next){
		cur[u]=i;
		int v=e[i].v;
		if(!e[i].w||d[v]!=d[u]+1)
			continue;
		int k=dfs(v,min(z,e[i].w));
		z-=k,e[i].w-=k,e[i^1].w+=k,awa+=k;
	}
	if(!z)
		d[u]=0;
	return awa;
}
int dinic()
{
	int awa=0;
	while(bfs())
		awa+=dfs(1,1e12);
	return awa;
}
signed main()
{
	s=read();
	t=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u,v;
		u=read();
		v=read()+s;
		if(u>s||v>s+t)
			continue;
		add(u,v,1);
		add(v,u,0);
	}
	for(int i=1;i<=s;i++)
		add(0,i,1),add(i,0,0);
	for(int i=s+1;i<=s+t;i++)
		add(i,s+t+1,1),add(s+t+1,i,0);
	printf("%lld\n",dinic());
	return 0;
}
2025/6/18 08:10
加载中...