有上下界限制可行流

無源匯有上下界限制可行流（循環流）

即每條邊的流量限制為[L,R]，判斷有沒有滿足整個網絡的可行流。

看看以前學的網絡流，實際上它的流量限制為[0,C]，現在無非多了一個下限的限制。

網絡流的一個重要性質：除了源匯點的點，入流==出流。

本來點是不能存儲水的，我們先不妨假設每條邊都滿足下限，對于某一條邊來說，它的出水端的點水量-=L，入水端的點+=L，它的容量變為[0,R-L]。

這時候就會出現有的點水量是正的，另外點的水量是負的，如果能通過導流，使所有點的水量均為0，那么說明存在可行流。

怎么導流？建立一個超級源點s，超級匯點t，s向水量為正的點連邊，容量即為水量。水量為負的點向t連邊，容量即為水量。（自己腦補）

s到t跑一遍最大流，如果最大流為源點流出的水量之和，則存在可行流。。

有源匯的情況：匯點向源點連一條容量INF的邊，即變成了無源匯的情況。

2018沈陽icpc網賽F（裸題）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef  long long ll;
const int MAX_N = 5000;  
const int MAX_M = 50000;  
const int INF = 1000000000;  
struct edge {
    int v, c, next;   
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {  
    e[eid].v = v;
    e[eid].c = c;
    e[eid].next = p[u];
    p[u] = eid++;
}
void addedge(int u, int v, int c) {  
    insert(u, v, c);
    insert(v, u, 0);  
}
int S, T;  
int d[MAX_N];  
bool CountLayer() {  
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].c > 0 && d[v] == -1) {
                q.push(v);
                d[v] = d[u] + 1;
            }
        }
    }
    return (d[T] != -1);  
}

ll dfs(int u, int flow) {  
    if (u == T) {
        return flow;
    }
    ll res = 0;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (e[i].c > 0 && d[u] + 1 == d[v]) {
            ll tmp = dfs(v, min(flow, e[i].c));  
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i ^ 1].c += tmp;  
            if (flow == 0) {  
                break;
            }
        }
    }
    if (res == 0) {  
        d[u] = -1;
    }
    return res;
}

ll maxflow() {  
    ll res = 0;
    while (CountLayer()) {
        res += dfs(S, INF);  
    }
    return res;
}
ll def[5000];
int main()
{   
    int d=1; 
    int n,m,k;
    while(cin>>n>>m>>k)
    {
        int l,r,u,v;
        S=n+m+3,T=n+m+4;
        init();
        memset(def,0,sizeof def);
        scanf("%d%d",&l,&r);
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&u,&v);
            v=v+n;
            addedge(u, v, 1);
        }
        for(int i=1;i<=n;i++)
        {
            addedge(n+m+1, i, r-l);
            def[i]+=l;
        }
        for(int i=n+1;i<=n+m;i++)
        {
            addedge(i, n+m+2, r-l);
            def[i]-=l;
        }
        addedge(n+m+2,n+m+1,INF);
       
        ll sum=0;
        for(int i=1;i<=n+m;i++)
        {
            if(def[i]>0) {addedge(S,i,def[i]);sum+=def[i];}
            else addedge(i,T,-def[i]);
        }
        if(sum==maxflow()) printf("Case %d: Yes\n",d++);
        else printf("Case %d: No\n",d++);
    }
    return 0;
}

?