loj #117. 有源汇有上下界最小流

题目链接

有源汇有上下界最小流，->上下界网络流

注意细节，边数组也要算上后加到SS，TT边。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N = ;

 const int INF = 1e9;

 struct Edge{

     int to,nxt,c;

 }e[];

 int head[N],dis[N],cur[N],M[N];

 int q[],L,R;

 int tot = ,n,m,S,T,Sum;

 inline char nc() {

     static char buf[],*p1 = buf,*p2 = buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

 }

 inline int read() {

     int x = ,f = ;char ch = nc();

     for (; ch<''||ch>'';ch=nc()) if(ch=='-') f=-;

     for (; ch>=''&&ch<=''; ch=nc()) x=x*+ch-'';

     return x * f;

 }

 void add_edge(int u,int v,int c) {

     e[++tot].to = v,e[tot].c = c,e[tot].nxt = head[u],head[u] = tot;

 }

 bool bfs() {

     for (int i=; i<=n+; ++i)

         cur[i] = head[i],dis[i] = -;

     L = ,R = ;

     q[++R] = S;

     dis[S] = ;

     while (L <= R) {

         int u = q[L++];

         for (int i=head[u]; i; i=e[i].nxt) {

             int v = e[i].to;

             if (dis[v] == - && e[i].c > ) {

                 dis[v] = dis[u] + ;

                 q[++R] = v;

                 if (v == T) return true;

             }

         }

     }

     return false;

 }

 int dfs(int u,int flow) {

     if (u == T) return flow;

     int used = ;

     for (int &i=cur[u]; i; i=e[i].nxt) {

         int v = e[i].to;

         if (dis[v] == dis[u] +  && e[i].c > ) {

             int tmp = dfs(v,min(e[i].c,flow-used));

             if (tmp > ) {

                 e[i].c -= tmp;e[i^].c += tmp;

                 used += tmp;

                 if (used == flow) break;

             }

         }

     }

     if (used != flow) dis[u] = -;

     return used;

 }

 int dinic(int s,int t) {

     S = s,T = t;

     int ans = ;

     while (bfs()) ans += dfs(S,INF);

     return ans;

 }

 int main () {

     n = read(),m = read();

     int s = read(),t = read();

     int ss = n + ,tt = n + ;

     for (int i=; i<=m; ++i) {

         int u = read(),v = read(),b = read(),c = read();

         add_edge(u,v,c-b);

         add_edge(v,u,);

         M[u] -= b;M[v] += b;

     }

     for (int i=; i<=n; ++i) {

         if (M[i] > ) add_edge(ss,i,M[i]),add_edge(i,ss,),Sum += M[i];

         if (M[i] < ) add_edge(i,tt,-M[i]),add_edge(tt,i,);

     }

     add_edge(t,s,INF); //-

     add_edge(s,t,);

     if (dinic(ss,tt) != Sum) {

         printf("please go home to sleep");

         return ;

     }

     int ans = e[tot].c;

     e[tot].c = ;e[tot ^ ].c = ;

     ans -= dinic(t,s);

     printf("%d",ans);

     return ;

 }