就是数据范围大了一些。另外注意把边数和点数卡死。我代码的数组就体现了这一过程。
#include<bits/stdc .h>
using namespace std;
const int inf=1000000007;
const int N=40010;
const int M=20010;
int maxflow,s,t;
int head[N],num_edge=1,cur[N],dep[N];
bool inq[N];
vector<int>g[N];
struct edge {
int nxt,val,to;
} e[(N N N M M)<<1];
void add(int from,int to,int val) {
num_edge;
e[num_edge].nxt=head[from];
e[num_edge].to=to;
e[num_edge].val=val;
head[from]=num_edge;
}
bool bfs() {
for(int i=1; i<=t; i)
inq[i]=false,cur[i]=head[i],dep[i]=inf;
queue<int>q;
q.push(s);
dep[s]=0;
inq[s]=true;
while(!q.empty()) {
int u=q.front();
q.pop();
inq[u]=false;
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(dep[v]>dep[u] 1&&e[i].val) {
dep[v]=dep[u] 1;
if(!inq[v]) {
q.push(v);
inq[v]=true;
}
}
}
}
return dep[t]!=inf;
}
int dfs(int u,int flow) {
if(u==t) {
maxflow =flow;
return flow;
}
int used=0,rlow;
for(int i=cur[u]; i; i=e[i].nxt) {
cur[u]=i;
int v=e[i].to,w=e[i].val;
if(w&&dep[v]==dep[u] 1) {
rlow=dfs(v,min(flow-used,w));
if(rlow) {
used =rlow;
e[i].val-=rlow;
e[i^1].val =rlow;
if(used==flow)break;
}
}
}
return used;
}
void dinic() {
while(bfs())dfs(s,inf);
}
int n1,n2,n3,m1,m2;
int main() {
scanf("%d%d%d",&n1,&n2,&n3);
s=n2 n1 n3 n1 1;t=s 1;
for(int i=n2 1;i<=n2 n1; i)
add(i,i n1 n3,1),add(i n1 n3,i,0);
for(int i=1;i<=n2; i)
add(s,i,1),add(i,s,0);
for(int i=n2 n1 1;i<=n2 n1 n3; i)
add(i,t,1),add(t,i,0);
scanf("%d",&m1);
for(int i=1,x,y;i<=m1; i)
{
scanf("%d%d",&x,&y);
add(y,x n2,1),add(x n2,y,0);
}
scanf("%d",&m2);
for(int i=1,x,y;i<=m2; i)
{
scanf("%d%d",&x,&y);
add(x n2 n1 n3,y n2 n1,1),add(y n2 n1,x n2 n1 n3,0);
}
dinic();
printf("%dn",maxflow);
return 0;
}