java網絡流最大流代碼 java 網絡流

java httpserveletresponse文件流最大是多少

ServletResponse中定義了如下兩個方法

專業成都網站建設公司，做排名好的好網站，排在同行前面，為您帶來客戶和效益!成都創新互聯公司為您提供成都網站建設，五站合一網站設計制作，服務好的網站設計公司，網站設計、成都網站建設負責任的成都網站制作公司!

getOutputStream();

getWriter();

對應獲得字節流和字符流

由于HttpServletResponse繼承自ServletResponse所以天生也具有以上兩個獲得輸出流的方法

怎么樣求網絡的最大流和最小截集

首先是網絡流中的一些定義：

V表示整個圖中的所有結點的集合.

E表示整個圖中所有邊的集合.

G = (V,E) ,表示整個圖.

s表示網絡的源點,t表示網絡的匯點.

對于每條邊(u,v),有一個容量c(u,v) (c(u,v)=0)，如果c(u,v)=0，則表示(u,v)不存在在網絡中。相反，如果原網絡中不存在邊(u,v)，則令c(u,v)=0.

對于每條邊(u,v),有一個流量f(u,v).

一個簡單的例子.網絡可以被想象成一些輸水的管道.括號內右邊的數字表示管道的容量c,左邊的數字表示這條管道的當前流量f.

網絡流的三個性質：

1、容量限制: f[u,v]=c[u,v]

2、反對稱性：f[u,v] = - f[v,u]

3、流量平衡: 對于不是源點也不是匯點的任意結點,流入該結點的流量和等于流出該結點的流量和。

只要滿足這三個性質,就是一個合法的網絡流.

最大流問題，就是求在滿足網絡流性質的情況下，源點 s 到匯點 t 的最大流量。

求一個網絡流的最大流有很多算法這里首先介紹增廣路算法（EK）

學習算法之前首先看了解這個算法中涉及到的幾個圖中的定義：

**殘量網絡

為了更方便算法的實現，一般根據原網絡定義一個殘量網絡。其中r(u,v)為殘量網絡的容量。

r(u,v) = c(u,v) – f(u,v)

通俗地講：就是對于某一條邊（也稱弧），還能再有多少流量經過。

Gf 殘量網絡,Ef 表示殘量網絡的邊集.

這是上面圖的一個殘量網絡。殘量網絡（如果網絡中一條邊的容量為0,則認為這條邊不在殘量網絡中。

r(s,v1)=0,所以就不畫出來了。另外舉個例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.

其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s還可以增加4單位的流量。

但是從v1到s不是和原網絡中的弧的方向相反嗎？顯然“從v1到s還可以增加4單位流量”這條信息毫無意義。那么，有必要建立這些后向弧嗎？

顯然，第1個圖中的畫出來的不是一個最大流。

但是，如果我們把s - v2 - v1 - t這條路徑經過的弧的流量都增加2,就得到了該網絡的最大流。

注意到這條路徑經過了一條后向弧:(v2,v1)。

如果不設立后向弧，算法就不能發現這條路徑。

**從本質上說，后向弧為算法糾正自己所犯的錯誤提供了可能性，它允許算法取消先前的錯誤的行為（讓2單位的流從v1流到v2)

注意,后向弧只是概念上的,在程序中后向弧與前向弧并無區別.

**增廣路

增廣路定義：在殘量網絡中的一條從s通往t的路徑，其中任意一條弧(u,v)，都有r[u,v]0。

如圖綠色的即為一條增廣路。

看了這么多概念相信大家對增廣路算法已經有大概的思路了吧。

**增廣路算法

增廣路算法：每次用BFS找一條最短的增廣路徑，然后沿著這條路徑修改流量值（實際修改的是殘量網絡的邊權）。當沒有增廣路時，算法停止，此時的流就是最大流。

**增廣路算法的效率

設n = |V|, m = |E|

每次增廣都是一次BFS,效率為O(m),而在最壞的情況下需要（n-2增廣。（即除源點和匯點外其他點都沒有連通，所有點都只和s與t連通）

所以,總共的時間復雜度為O(m*n)，所以在稀疏圖中效率還是比較高的。

hdoj 1532是一道可以作為模板題目練手。

模板代碼：

[cpp] view plain copy print?

#include cstdio

#include cstring

#include iostream

#include string

#include algorithm

#include map

#include vector

using namespace std;

const int N = 1100;

const int INF = 0x3f3f3f3f;

struct Node

{

int to;//終點

int cap; //容量

int rev; //反向邊

};

vectorNode v[N];

bool used[N];

void add_Node(int from,int to,int cap) //重邊情況不影響

{

v[from].push_back((Node){to,cap,v[to].size()});

v[to].push_back((Node){from,0,v[from].size()-1});

}

int dfs(int s,int t,int f)

{

if(s==t)

return f;

used[s]=true;

for(int i=0;iv[s].size();i++)

{

Node tmp = v[s][i]; //注意

if(used[tmp.to]==false tmp.cap0)

{

int d=dfs(tmp.to,t,min(f,tmp.cap));

if(d0)

{

tmp.cap-=d;

v[tmp.to][tmp.rev].cap+=d;

return d;

}

return 0;

}

int max_flow(int s,int t)

{

int flow=0;

for(){

memset(used,false,sizeof(used));

int f=dfs(s,t,INF);

if(f==0)

return flow;

flow+=f;

}

int main()

{

int n,m;

while(~scanf("%d%d",n,m))

{

memset(v,0,sizeof(v));

for(int i=0;in;i++)

{

int x,y,z;

scanf("%d%d%d",x,y,z);

add_Node(x,y,z);

}

printf("%d\n",max_flow(1,m));

}

最大網絡流問題，誰能幫我把題目的代碼寫一下，用c++或c寫。題目如下：

#includeiostream

#includequeue

using namespace std;

#define INF 1000000000

struct node{

int from;

int to;

int flow;

}f[1000];

int n,m;

int maxf[1000];

bool vis[1000];

void bfs()

{

queueint p;

int i;

vis[1]=true;

p.push(1);

while(!p.empty())

{

int q=p.front();

p.pop();

for(i=1;i=m;i++)

{

if(f[i].from==q)

{

if(vis[f[i].to]==0)

{

p.push(f[i].to);

vis[f[i].to]=true;

}

maxf[f[i].to]+=min(f[i].flow,maxf[q]);

}

coutmaxf[n]endl;

}

int main()

{

while(cinnm)

{

int i;

for(i=1;i=m;i++)

{

cinf[i].fromf[i].tof[i].flow;

}

memset(maxf,0,sizeof(maxf));

memset(vis,0,sizeof(vis));

maxf[1]=INF;

bfs();

}

return 0;

}

BFS解最大流。

網絡流的最大流算法

1、augment path，直譯為“增廣路徑”，其思想大致如下：

原有網絡為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑，然后將該路徑上所有的容量減去該路徑上容量的最小值，然后對路徑上每一條邊u,v添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。

我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網絡中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。

尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。

增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個復雜得多的算法，就是預推進算法。

2、push label，直譯為“預推進”算法。

3、壓入與重標記(Push-Relabel)算法

除了用各種方法在剩余網絡中不斷找增廣路(augmenting)的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有：壓入，作用于一條邊，將邊的始點的預流盡可能多的壓向終點；重標記，作用于一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點是相對難以理解。

Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。算法的主過程是：首先將源點出發的所有邊充滿，然后將除源和匯外的所有頂點保存在一個鏈表里，從鏈表頭開始進行Discharge，如果完成后頂點的高度有所增加，則將這個頂點置于鏈表的頭部，對下一個頂點開始Discharge。

Relabel-to-Front算法的時間復雜度是O(V^3)，還有一個叫Highest Label Preflow Push的算法復雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當于每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。

Push-Relabel類的算法有一個名為gap heuristic的優化，就是當存在一個整數0kV，沒有任何頂點滿足h[v]=k時，對所有h[v]k的頂點v做更新，若它小于V+1就置為V+1。

cpp程序: #includecstdio#includecstring#includealgorithm#includequeue#define?inf?0x7fffffffusingnamespace?std;int?tt,kase;int?nn,m;int?H[45],X[1004],P[1004],flow[1004],tot,cap[1005];int?d[45];int?S,T;void?add(int?x,int?y,int?z){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queueint?q;bool?bfs(){memset(d,0,sizeof(d));d[S]=1;?int?x;q.push(S);while(!q.empty()){x=q.front();q.pop();for(int?i=H[x];i;i=X[i]){if(flow[i]0!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}int?dfs(int?x,int?a){if(x==T||a==0)return?a;int?f=a,tmp;for(int?i=H[x];i;i=X[i]){if(flow[i]0d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;return?f-a;}int?Dinic(){int?f=0;while(bfs())f+=dfs(S,inf);return?f;}int?main(){/**輸入過程省略**/int?maxflow=Dinic();printf(%d\n,maxflow);return?0;}

網站標題：java網絡流最大流代碼 java 網絡流
網站鏈接：http://vcdvsql.cn/article46/ddeephg.html

成都網站建設公司_創新互聯，為您提供服務器托管、微信小程序、網站改版、網站內鏈、品牌網站制作、網站維護