好久没打网络流了,为什么 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;
}