妈耶
我的图建反了两次 准确的说是有两个地方建反了，然后反上加反改了一个小时……
知道为什么要拆点吗？
假设这是你的图 左边到右边依次是超级源点 练习册 书 答案 超级汇点
请问这张图的最大流是多少？
如果把中间拆成这样：
Book-in是跟练习册匹配的书的入端，Book-out是跟答案匹配的书的出端。相当于每本书都是一条隧道，有入口有出口，每本书的入口和对应的出口连边。
请问现在这张图的最大流是多少？
所以你看。
代码放上：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cctype> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int next,to,val; }edge[2000010]; int head[200010],num=-1; inline void add(int from,int to,int val){ edge[++num]=(Edge){ head[from],to,val}; head[from]=num; } bool vis[200010]; int dfn[200010]; int list[200010]; int f[200010],h,t=1; int n,m,Start,End; bool bfs(){ memset(vis,0,sizeof(vis)); f[1]=Start;vis[Start]=1;dfn[Start]=1;h=0;t=1; while(h++<t){ int from=f[h]; for(int i=head[from];i!=-1;i=edge[i].next){ int to=edge[i].to; if(vis[to]||(!edge[i].val)) continue; dfn[to]=dfn[from]+1; vis[to]=1; f[++t]=to; } } return vis[End]; } int dfs(int x,int val){ if(x==End||val==0) return val; int flow=0; vis[x]=1; for(int &i=list[x];i!=-1;i=edge[i].next){ int to=edge[i].to; if(dfn[to]==dfn[x]+1&&!vis[to]&&edge[i].val>0){ int now=dfs(to,std::min(edge[i].val,val)); if(now>0){ edge[i].val-=now; edge[i^1].val+=now; flow+=now;val-=now; if(val<=0) break; } } } if(flow!=val) dfn[x]=-1; return flow; } int ans; int main(){ memset(head,-1,sizeof(head)); int n1=read(),n2=read(),n3=read(); int n=n1*2+n2;int N=n+n3;End=N+1; int m1=read(); for(int i=1;i<=m1;++i){ int book=read(),note=read(); add(note+n1*2,book,1); add(book,note+n1*2,0); } int m2=read(); for(int i=1;i<=m2;++i){ int book=read(),ansnote=read(); add(book+n1,ansnote+n,1); add(ansnote+n,book+n1,0); } for(int i=1;i<=n1;++i){ add(i,i+n1,1); add(i+n1,i,0); } for(int i=1;i<=n2;++i){ add(Start,i+n1*2,1); add(i+n1*2,Start,0); } for(int i=1;i<=n3;++i){ add(i+n,End,1); add(End,i+n,0); } while(bfs()){ memset(vis,0,sizeof(vis)); for(int i=0;i<=End;++i) list[i]=head[i]; int now=dfs(Start,0x7fffffff); if(!now) break; ans+=now; } printf("%d",ans); return 0; }
话说当前弧优化真好用