焦作维科网站建设公司,没有域名可以先做网站吗,临汾哪里有做网站的,互联网+可以做什么项目1 /*2 题意#xff1a;无源无汇#xff0c;并且每条边的容量有上下界限的网络流问题#xff01;既然无源无汇#xff0c;那么素有的节点都应该满足“入流出流”#xff01;3 输出每一条边的流量#xff0c;使得满足上面的条件。#xff08;如果u-v有流… 1 /*2 题意无源无汇并且每条边的容量有上下界限的网络流问题既然无源无汇那么素有的节点都应该满足“入流出流”3 输出每一条边的流量使得满足上面的条件。如果u-v有流量那么v-u就不会有流量4 5 思路如果增加了源点s和汇点t对于u-v下限为l 上限为f 将这一条边拆成3条s-v(容量为l) u-v(容量为f-l)6 u-t(容量为l)这样就变成了每一个点的流入或者流出的流量至少是b然后从s-t走一遍最大流如果所有的附件边都已经7 满载则就是所有s-v的边和u-t的边或者只判断其中一者就可以那么就存在答案8 */9 #includeiostream10 #includecstdio11 #includecstring12 #includealgorithm13 #includevector14 #includequeue15 #define INF 0x3f3f3f3f16 #define N 20517 #define M 50000018 using namespace std;19 20 struct EDGE{21 int v, cap, tot, nt, b;22 EDGE(){};23 EDGE(int v, int cap, int nt, int b) : v(v), cap(cap), nt(nt), b(b), tot(cap){}24 };25 26 EDGE edge[M];27 int n, m;28 int first[N];29 int pre[N], d[N];30 int sz;31 int s, t;32 int full, fout; 33 34 void addEdge(int u, int v, int b, int cap){35 edge[sz] (EDGE(v, cap, first[u],b));36 first[u] sz;37 edge[sz] (EDGE(u, 0, first[v], 0));38 first[v] sz;39 40 edge[sz] (EDGE(v, b, first[s], 0));41 first[s] sz;42 edge[sz] (EDGE(s, 0, first[v], 0));43 first[v] sz;44 45 edge[sz] (EDGE(t, b, first[u], 0));46 full b;47 first[u] sz;48 edge[sz] (EDGE(u, 0, first[t], 0));49 first[t] sz;50 }51 52 bool bfs(){53 queueintq;54 memset(d, 0, sizeof(d));55 d[s] 1;56 q.push(s);57 while(!q.empty()){58 int u q.front(); q.pop();59 for(int i first[u]; ~i; i edge[i].nt){60 int v edge[i].v;61 if(!d[v] edge[i].cap 0){62 d[v] d[u] 1;63 q.push(v);64 }65 }66 }67 if(d[t] 0) return false;68 return true;69 }70 71 int dfs(int u, int totf){72 int ff;73 if( u t) return totf;74 int flow 0;75 for(int i first[u]; ~i totf flow; i edge[i].nt){76 int v edge[i].v;77 int cap edge[i].cap;78 //流入u节点的当前总的流量为totf可以得到 u-v1, u-v2, u-v3....这些路径上的最大流的和为flowfu-vi79 //f(u-vi)表示u节点沿着vi节点方向的路径上的最大流如果u-vi1的容量为wi1那么u-vi1所允许流过的最大80 //的流量就是 min(totf - cost, wi1)了81 if(d[v] d[u] 1 cap 0 ){82 ff dfs(v, min(totf - flow, cap));83 if(ff){84 edge[i].cap - ff;85 edge[i^1].cap ff;86 flow ff;87 }88 else89 d[v] -1;//表示v这个点无法在继续增广下去了90 }91 }92 return flow;//返回从u节点向外流出的最大流量93 }94 95 bool Dinic(){96 while(bfs())97 fout dfs(0, INF);//这一块没想到写成whiledfs会超时....98 99 if( fout ! full) return false;
100 return true;
101 }
102
103 int main(){
104
105 scanf(%d%d, n, m);
106 memset(first, -1, sizeof(first));
107 sz 0;
108 fout full 0;
109 s 0; t n1;
110 int u, v, l, f;
111 for(int i 1; i m; i){
112 scanf(%d%d%d%d, u, v, l, f);
113 addEdge(u, v, l, f-l);
114 }
115 if(!Dinic()){
116 printf(NO\n);
117 return 0;
118 }
119 printf(YES\n);
120 for(int i 1; i m; i){
121 int j (i-1)*6;
122 printf(%d\n, edge[j].tot - edge[j].cap edge[j].b);//输出这条边实际流过的流量下限
123 }
124
125 return 0;
126 } 转载于:https://www.cnblogs.com/hujunzheng/p/4006435.html
