模板无源汇上下界可行流 loj115

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 const int maxn = 210,maxm = 20800,inf = 1000000000;
  6 int cnt = 1,ss,tt,n,m;
  7 int head[maxn],dis[maxn],d[maxn],nxt[maxm],to[maxm],flow[maxm],low[maxm];
  8 bool inq[maxn]; 
  9 void add(int a,int b,int fl)
 10 {
 11     nxt[++cnt] = head[a];
 12     to[cnt] = b;
 13     head[a] = cnt;
 14     flow[cnt] = fl;
 15     nxt[++cnt] = head[b];
 16     to[cnt] = a;
 17     head[b] = cnt;
 18     flow[cnt] = 0;
 19 }
 20   
 21 bool bfs()
 22 {
 23     queue <int> que;
 24     memset(inq,0,sizeof(inq));
 25     que.push(tt);
 26     inq[tt] = 1;
 27     while (!que.empty())
 28     {
 29         int cur = que.front();
 30         que.pop();
 31         for (int i = head[cur];i;i = nxt[i])
 32         {
 33             int v = to[i];
 34             if (!inq[v] && flow[i ^ 1])
 35             {
 36                 dis[v] = dis[cur] + 1;
 37                 que.push(v);
 38                 inq[v] = 1;
 39             }
 40         }
 41     }
 42     return inq[ss];
 43 }
 44 int dfs(int cur,int lmt)
 45 {
 46     if (cur == tt) return lmt;
 47     int fl = 0;
 48     for (int i = head[cur];i && fl < lmt;i = nxt[i])
 49     {
 50         if (dis[to[i]] + 1 == dis[cur] && flow[i])
 51         {
 52             int tt = dfs(to[i],min(lmt - fl,flow[i]));
 53             flow[i] -= tt;
 54             flow[i ^ 1] += tt;
 55             fl += tt;
 56         }   
 57     }
 58     return fl;
 59 }
 60 int maxflow()
 61 {
 62     int res = 0;
 63     while (bfs())
 64     {
 65         int fl = 0;
 66         do
 67         {
 68             fl = dfs(ss,inf);
 69             res += fl;
 70         } while (fl);
 71     }
 72     return res;
 73 }
 74 //cnt = 1
 75 int main()
 76 {
 77     scanf("%d%d",&n,&m);
 78     ss = n + 1;
 79     tt = n + 2;
 80     int tx,ty,tl,tu;
 81     for (int i = 1;i <= m;i++)
 82     {
 83         scanf("%d%d%d%d",&tx,&ty,&tl,&tu);
 84         add(tx,ty,tu - tl);
 85         d[tx] -= tl;
 86         d[ty] += tl;
 87         low[i] = tl;
 88     }
 89     int sum = 0;
 90     for (int i = 1;i <= n;i++)
 91         if (d[i] > 0)
 92         {
 93             sum += d[i];
 94             add(ss,i,d[i]);
 95         }else if (d[i] < 0)
 96             add(i,tt,-d[i]); 
 97     if (maxflow() != sum)
 98     {
 99         printf("NO
");
100         return 0;
101     }else
102     {
103         printf("YES
");
104         for (int i = 1;i <= m;i++)
105             printf("%d
",flow[i * 2 | 1] + low[i]);
106     }
107     return 0;
108 }
心之所动且就随缘去吧
模板 无源汇上下界可行流 loj115

模板无源汇上下界可行流 loj115
