加从t到s的流量无穷大，然后在可行流的残留网络上跑最大流。
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 210,maxm = 20800,inf = 1000000000; int cnt = 1,ss,tt,s,t,n,m; int head[maxn],dis[maxn],d[maxn],nxt[maxm],to[maxm],flow[maxm],low[maxm]; bool inq[maxn]; void add(int a,int b,int fl) { nxt[++cnt] = head[a]; to[cnt] = b; head[a] = cnt; flow[cnt] = fl; nxt[++cnt] = head[b]; to[cnt] = a; head[b] = cnt; flow[cnt] = 0; } bool bfs() { queue <int> que; memset(inq,0,sizeof(inq)); que.push(tt); inq[tt] = 1; while (!que.empty()) { int cur = que.front(); que.pop(); for (int i = head[cur];i;i = nxt[i]) { int v = to[i]; if (!inq[v] && flow[i ^ 1]) { dis[v] = dis[cur] + 1; que.push(v); inq[v] = 1; } } } return inq[ss]; } int dfs(int cur,int lmt) { if (cur == tt) return lmt; int fl = 0; for (int i = head[cur];i && fl < lmt;i = nxt[i]) { if (dis[to[i]] + 1 == dis[cur] && flow[i]) { int tt = dfs(to[i],min(lmt - fl,flow[i])); flow[i] -= tt; flow[i ^ 1] += tt; fl += tt; } } return fl; } int maxflow() { int res = 0; while (bfs()) { int fl = 0; do { fl = dfs(ss,inf); res += fl; } while (fl); } return res; } //cnt = 1 int main() { scanf("%d%d%d%d",&n,&m,&s,&t); ss = n + 1; tt = n + 2; int tx,ty,tl,tu; for (int i = 1;i <= m;i++) { scanf("%d%d%d%d",&tx,&ty,&tl,&tu); add(tx,ty,tu - tl); d[tx] -= tl; d[ty] += tl; low[i] = tl; } add(t,s,inf); int sum = 0; for (int i = 1;i <= n;i++) if (d[i] > 0) { sum += d[i]; add(ss,i,d[i]); }else if (d[i] < 0) add(i,tt,-d[i]); if (maxflow() != sum) { printf("please go home to sleep\n"); return 0; }else { ss = s; tt = t; printf("%d\n",maxflow()); } return 0; }