首页 > 代码库 > zoj 2314Reactor Cooling

zoj 2314Reactor Cooling

2024-09-04 02:23:25   223人阅读

 秘制神奇上下界网络流%%%

什么什么有（木）源汇可行流什么的，，看不懂（一下纯属个人sb言论）

看了半天知道点，一个点u，从S连到u的流量是全部流入u的下界，u到T是全部流出u的下界和。（进去出来的约一下）

感觉这个的意思就是保持从进入到出来的下界都符合（强行构造相等？？），并且如果能满流，则上界也符合。那么就是可行的。

看了个有上下界最大流什么的，连一个从T-S的边，然后原图就成了无原汇了，那么再加TT，SS，搞上面的，判断可行的同时可以得出来S-T的流量，是一个可行流量。设为sum1.

那么去掉S-T的边和SS，TT点，在跑了一遍的图上跑最大流，就是使原有的图继续增广，可以得出另一个最大流sum2，那么ans=sum1+sum2。（就看了这么一点，sb）

  1 #include<bits/stdc++.h>
  2 #define N 100005
  3 #define LL long long
  4 #define inf 0x3f3f3f3f
  5 #define ls tr[x][0]
  6 #define rs tr[x][1]
  7 using namespace std;
  8 inline int ra()
  9 {
 10     int x=0,f=1; char ch=getchar();
 11     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
 12     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
 13     return x*f;
 14 }
 15 const int S=0,T=201;
 16 int n,m,cnt;
 17 int head[205],cur[205],h[205],q[2050],in[205];
 18 int low[100005];
 19 struct data{int to,next,v;}e[100005];
 20 void ine(int x, int y, int v)
 21 {
 22     e[++cnt].to=y;
 23     e[cnt].next=head[x];
 24     e[cnt].v=v;
 25     head[x]=cnt;
 26 }
 27 void insert(int x, int y, int v)
 28 {
 29     ine(x,y,v); ine(y,x,0);
 30 }
 31 bool bfs()
 32 {
 33     for (int i=1; i<=T; i++) h[i]=-1;
 34     int l=0,r=1; q[0]=S; h[S]=0;
 35     while (l<r)
 36     {
 37         int x=q[l++];
 38         for (int i=head[x];i;i=e[i].next)
 39             if (e[i].v && h[e[i].to]==-1)
 40             {
 41                 h[e[i].to]=h[x]+1;
 42                 q[r++]=e[i].to;
 43             }
 44     }
 45     if (h[T]==-1) return 0;
 46     return 1;
 47 }
 48 int dfs(int x, int f)
 49 {
 50     if (x==T) return f;
 51     int w,ww=0;
 52     for (int i=head[x];i;i=e[i].next)
 53         if (h[e[i].to]==h[x]+1)
 54         {
 55             w=dfs(e[i].to,min(e[i].v,f-ww));
 56             ww+=w; e[i].v-=w; e[i^1].v+=w;
 57             if (ww==f) return f;
 58         }
 59     if (!ww) h[x]=-1;
 60     return ww;
 61 }
 62 void dinic()
 63 {
 64     while (bfs()) dfs(S,inf);
 65 }
 66 void build()
 67 {
 68     for (int i=1; i<=n; i++)
 69         if (in[i]>0) insert(S,i,in[i]);
 70             else insert(i,T,-in[i]);
 71 }
 72 bool jud()
 73 {
 74     for (int i=head[S];i;i=e[i].next)
 75         if (e[i].v) return 0;
 76     return 1;
 77 }
 78 int main()
 79 {
 80     int t=ra();
 81     while (t--)
 82     {
 83         cnt=1;
 84         memset(head,0,sizeof(head));
 85         memset(in,0,sizeof(in));
 86         n=ra(); m=ra();
 87         for (int i=1; i<=m; i++)
 88         {
 89             int x=ra(),y=ra(); low[i]=ra(); int w=ra();
 90             in[x]-=low[i]; in[y]+=low[i];
 91             insert(x,y,w-low[i]);
 92         }
 93         build(); dinic();
 94         if (!jud()) cout<<"NO"<<endl;
 95         else{
 96             cout<<"YES"<<endl;
 97             for (int i=1; i<=m; i++)
 98                 printf("%d\n",e[(i<<1)^1].v+low[i]);
 99         }
100         cout<<endl;
101     }
102     return 0;
103 }

 

zoj 2314Reactor Cooling


联系
我们