首页 > 代码库 > 萌萌的网络流~~
萌萌的网络流~~
上下界网络流：
sgu 194 （无源汇的上下界网络流）：
题意：给出一个网络，每条边有上下界，问是否存在可行流。如果存在，输出经过每条边的流量。
建图：每条边必须有li的流量，那么新建超级源点和超级汇点，然后统计每个点的“入度”和“出度”，然后源点和每个点建一条流量为“入度”的边，每个点和汇点建一条流量为“出度”的边。为了流量平衡，每条边取原有上界-原有下界为流量，然后加入网络。（还有种做法是每个点统计出度和入度，判断是正是负来决定它和源点还是汇点建边。这种做法运行效率更高一些。）
题目给的图因为没有源点和汇点，所以我觉得统计最大流是没有意义的。对于我们自己建的图，判断一下每条边的下界的和是否等于最大流，以此来判定是否有可行流就行了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <cstring> 6 #include <ctime> 7 #define FORD(i,r,l) for(int i=(r);i>=(l);i--) 8 #define rep(i,n) for(int i=0;i<(n);i++) 9 #define req(i,l,n) for(int i=(l);i<(n);i++)10 using namespace std;11 typedef long long LL;12 const int maxn=205+1,maxm=120000;13 const LL jx=0x7fffffffffffffff;14 15 int pos,ta[maxn],lin[maxm],sd[maxm],sl[maxm];16 void biu(int s,int t,int c)17 {18 ++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;19 ++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;20 }21 22 int nn;23 int h[maxn];24 int vh[maxn];25 int aug(int v,int deta)26 {27 if (v==nn) return deta;28 int mins=nn-1,augc,bak=deta;29 for (int i=ta[v];i;i=lin[i])30 if (sl[i])31 {32 if (h[v]==h[sd[i]]+1)33 {34 augc=min(deta,sl[i]);35 augc=aug(sd[i],augc);36 deta-=augc;37 sl[i]-=augc; sl[(i+1^1)-1]+=augc;38 if (!deta) break;39 if (h[nn-1]>=nn) return bak-deta;40 }41 mins=min(mins,h[sd[i]]);42 }43 if (bak==deta)44 {45 vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;46 h[v]=mins+1; vh[h[v]]++;47 }48 return bak-deta;49 }50 51 int n,m;52 int rd[201],cd[201];53 int pipel[maxm];54 int main(){55 scanf("%d%d",&n,&m);56 int u,v,l,c;57 for (int i=1;i<=m;i++)58 {59 scanf("%d%d%d%d",&u,&v,&l,&c);60 pipel[i]=l;61 rd[v]+=l; cd[u]+=l;62 biu(u,v,c-l);63 }64 nn=n+2;//--65 LL sum=0;66 for (int i=1;i<=n;i++)67 {68 if (rd[i]) biu(nn-1,i,rd[i]);69 if (cd[i]) biu(i,nn,cd[i]);70 sum+=rd[i];71 }72 LL flow=0;73 while (h[nn-1]<nn) flow+=aug(nn-1,0x7fffffff);74 if (sum!=flow) puts("NO\n");75 else76 {77 puts("YES");78 for (int i=1;i<=m;i++) printf("%d\n",pipel[i]+sl[i*2]);79 }80 return 0;81 }
（提示：如果第7个点WA了，说明你没开long long或者数组范围没够。）
萌萌的网络流~~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。