經(jīng)典的算法——網(wǎng)絡(luò)流

算法的精髓在于尋找一條可增廣路來擴增流量。

之后再同時更新這條增廣路上的正向反向邊。例題：

POJ 1273?Drainage Ditches

#include<cstring> #include<queue> #include<iostream> #include<cstdio> using namespace std; const int MAXN=500; const int M_MAX=1<<30; int pre[MAXN],vis[MAXN]; //pre表示當(dāng)前節(jié)點的 前一節(jié)點 vis表示是否訪問過 int dis[MAXN][MAXN],Mini[MAXN]; // 鄰接矩陣表示，Mini表示可以更新的最小流量 int m,n; //m表示邊數(shù),n表示點數(shù) int bfs() //尋找可增廣路 {int src=1,i;queue<int>q; //更新隊列q.push(src);vis[src]=1;pre[src]=0;Mini[src]=M_MAX;while(!q.empty()){int temp=q.front();q.pop();if(temp==n)break;for(i=1;i<=n;i++){if(vis[i]==0&&dis[temp][i]){vis[i]=1;q.push(i);pre[i]=temp;Mini[i]=min(Mini[temp],dis[temp][i]);}}}if(vis[n]==0) return -1;else return Mini[n]; } void EK() {int flow;int MAX_flow=0;while((flow=bfs())!=-1){int temp=n;memset(vis,0,sizeof(vis));MAX_flow+=flow;while(temp!=1){dis[pre[temp]][temp]-=flow; //正向流量變更dis[temp][pre[temp]]+=flow; //反向流量變更 temp=pre[temp];}}printf("%d\n",MAX_flow); } int main() {while(scanf("%d%d",&m,&n)!=EOF){int i,a,b,c;memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);dis[a][b]+=c; //重復(fù)管道}EK();} }

?

總結(jié)

以上是生活随笔為你收集整理的网络流EK算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。