貌似炸的很惨,一次dfs只能增加1最大流,有没有什么其他的优化?
(打了弧优化的啊)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int head[1000001],cnt,n,m,s,t,maxflow,dis[1000001],ans,vis,cur[1000001],pp,qq;
queue<int>q;
struct node
{
int to,dis,next;
}a[10000001];
void add_edge(int from,int to,int dis)
{
a[++cnt].to=to;
a[cnt].dis=dis;
a[cnt].next=head[from];
head[from]=cnt;
}
bool bfs()
{
//cout<<"bfs"<<endl;
for(int i=1;i<=n;i++)
{
cur[i]=head[i];
dis[i]=0;
}
while(!q.empty())q.pop();
q.push(s);
dis[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(a[i].dis&&!dis[v])
{
q.push(v);
dis[v]=dis[u]+1;
if(v==t)return 1;
}
}
}
return 0;
}
int luogu(int u,int flow_now)//返回u点使用了多少流量,flow_now为当前点可以使用的流量
{
//cout<<u<<endl;
//cout<<"dfs"<<endl;
if(u==t)
{
//vis=1;
return flow_now;
}
int k=0,used=0;
for(int i=cur[u];i;i=a[i].next)
{
cur[u]=i;
int v=a[i].to;
if(a[i].dis&&dis[v]==dis[u]+1)
{
k=luogu(v,min(flow_now-used,a[i].dis));
if(!k)dis[v]=0;
a[i].dis-=k;
a[i^1].dis+=k;
used+=k;
}
}
return used;
}
int main()
{
freopen("P1231_2.in","r",stdin);
freopen("Greg_Tech_No_Hope.txt","w",stdout);
int x,y;
cin>>n>>pp>>qq;
cnt++;
cin>>m;
for(int i=1;i<=n;i++)
{
add_edge(i,i+n,1);
add_edge(i+n,i,0);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_edge(y+2*n,x,1);
add_edge(x,y+2*n,0);
}
cin>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_edge(x+n,y+2*n+pp,1);
add_edge(y+2*n+pp,x+n,0);
}
for(int i=1;i<=pp;i++)
{
add_edge(2*n+pp+qq+1,i+2*n,1);
add_edge(i+2*n,2*n+pp+qq+1,0);
}
for(int i=1;i<=qq;i++)
{
add_edge(i+2*n+pp,2*n+pp+qq+2,1);
add_edge(2*n+pp+qq+2,i+2*n+pp,0);
}
s=2*n+pp+qq+1;
t=2*n+pp+qq+2;
n=2*n+pp+qq+2;
while(bfs())
{
//cout<<"bfs"<<endl;
while(1)
{
//cout<<"dfs"<<endl;
//vis=0;
ans=luogu(s,0x7fffffff);
if(!ans)break;
maxflow+=ans;
cout<<maxflow<<endl;
}
}
cout<<maxflow;
}