由于有多个源点和汇点,就考虑把所有源点变为从一个总源点来供应,所有汇点汇到一个总汇点,再写一个 Edmonds-Karp 即可。
#include"cstdio"#include"cctype"#include"cstring"#include"algorithm"using namespace std;int read(){ int c,x=0; while(!isdigit(c=getchar())); while(x=x*10+c-'0',isdigit(c=getchar())); return x;}int n,nc,np,m,s,t,vis[102],pre[102],f[102][102];int bfs(){ memset(vis,0,sizeof vis); memset(pre,0,sizeof pre); int q[102],l=0,r=0; vis[s]=1; q[r++]=s; while(l