a5源码网站/上海网络推广排名公司

就是由于下大雨的时候约翰的农场就会被雨水给淹没，无奈下约翰不得不修建水沟，而且是网络水沟，并且聪明的约翰还控制了水的流速，本题就是让你求出最大流速，无疑要运用到求最大流了。题中N为水沟数，M为水沟的顶点，接下来Si,Ei,Ci分别是水沟的起点，终点以及其容量。求源点1到终点M的最大流速。

ek:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define M 205
#define inf 1e8
int n,m,a,b,c,g[M][M],flow[M],pre[M];
bool vis[M];
int bfs()
{memset(vis,false,sizeof(vis));memset(pre,-1,sizeof(pre));for(int i=1;i<=n;i++)flow[i]=inf;vis[1]=true;queue<int>q;q.push(1);while(!q.empty()){int p=q.front();q.pop();for(int i=1;i<=n;i++){if(!vis[i]&&g[p][i]>0){vis[i]=true;flow[i]=min(flow[p],g[p][i]);pre[i]=p;q.push(i);}}}if(!vis[n]||n==1) return -1;return flow[n];
}
int ek()
{int maxflow=0,d,res,temp;while((d=bfs())!=-1){maxflow+=d;temp=n;while(temp!=1){res=pre[temp];g[res][temp]-=d;g[temp][res]+=d;temp=res;}}return maxflow;
}
int main()
{//freopen("in.txt","r",stdin);while(~scanf("%d%d",&m,&n)){memset(g,0,sizeof(g));while(m--){scanf("%d%d%d",&a,&b,&c);g[a][b]+=c;}printf("%d\n",ek());}return 0;
}

 dinic:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define M 205
#define inf 1e8
int n,m,dis[M],r,cur[M];
struct edge
{int u,v,cap;edge(){}edge(int a,int b,int c){u=a;v=b;cap=c;}
}eg[M*2];
vector<int>g[M];
void addedge(int a,int b,int c)
{g[a].push_back(r);eg[r++]=edge(a,b,c);g[b].push_back(r);eg[r++]=edge(b,a,0);
}
bool bfs()
{memset(dis,0,sizeof(dis));dis[1]=1;queue<int>q;q.push(1);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<g[x].size();i++){edge &e=eg[g[x][i]];if(!dis[e.v]&&e.cap>0){dis[e.v]=dis[x]+1;q.push(e.v);}}}return dis[n];
}
int dfs(int x,int low)
{if(x==n||!low) return low;int p;for(int i=cur[x];i<g[x].size();i++){cur[x]=i;edge &e=eg[g[x][i]];if(e.cap>0&&dis[e.v]==dis[x]+1&&(p=dfs(e.v,min(low,e.cap)))){e.cap-=p;eg[g[x][i]^1].cap+=p;return p;}}return 0;
}
void dinic()
{int ans=0,now;while(bfs()){memset(cur,0,sizeof(cur));while(now=dfs(1,inf)) ans+=now;}printf("%d\n",ans);
}
int main()
{//freopen("in.txt","r",stdin);while(~scanf("%d%d",&m,&n)){int a,b,c;r=0;for(int i=1;i<=n;i++)g[i].clear();while(m--){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}dinic();}return 0;
}

 isap:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
#define inf 1e8
#define maxm 400000
#define maxn 1100
int head[maxn],eid;
int dis[maxn];//残量网络中节点i到汇点t的最短距离
int num[maxn];//和t的最短距离等于i的节点数量
int cur[maxn];//当前弧下标
int pre[maxn];//可增广路上的上一条弧的编号
struct node
{int v,cap,next;
} edge[maxm];
void add(int u,int v,int cap)
{edge[eid].v=v;edge[eid].cap=cap;edge[eid].next=head[u];head[u]=eid++;edge[eid].v=u;edge[eid].cap=0;edge[eid].next=head[v];head[v]=eid++;
}
void bfs(int source,int sink)//预处理，利用反向BFS，更新dis数组
{queue<int>q;while(!q.empty()) q.pop();memset(num,0,sizeof(num));memset(dis,-1,sizeof(dis));q.push(sink);dis[sink]=0;num[0]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u]; i!=-1; i=edge[i].next){int v=edge[i].v;if(dis[v]==-1){dis[v]=dis[u]+1;//找允许弧num[dis[v]]++;q.push(v);}}}
}
int isap(int source,int sink,int n)//n为残量网络中的节点到汇点的最大距离，通常节点的个数，即上限
{memcpy(cur,head,sizeof(cur));int flow=0,u=pre[source]=source;bfs(source,sink);//更新dis数组while(dis[source]<n){if(u==sink){int df=inf,pos;for(int i=source;i!=sink;i=edge[cur[i]].v)//追踪增广路路径，最小残量df
            {if(df>edge[cur[i]].cap){df=edge[cur[i]].cap;pos=i;}}for(int i=source;i!=sink;i=edge[cur[i]].v)//更新流量
            {edge[cur[i]].cap-=df;edge[cur[i]^1].cap+=df;}flow+=df;u=pos;}int st;for(st=cur[u];st!=-1;st=edge[st].next)//从当前弧开始查找允许弧if(dis[edge[st].v]+1==dis[u]&&edge[st].cap)//找到允许弧跳出break;if(st!=-1){cur[u]=st;pre[edge[st].v]=u;u=edge[st].v;}else{if((--num[dis[u]])==0) break;//GAP优化,出现断层结束int mind=n;for(int id=head[u];id!=-1;id=edge[id].next)//retreat操作：更新dis数组
            {if(mind>dis[edge[id].v]&&edge[id].cap){cur[u]=id;//修改标号的同时修改当前弧mind=dis[edge[id].v];}}dis[u]=mind+1;num[dis[u]]++;if(u!=source) u=pre[u];// 回溯继续寻找允许弧
        }}return flow;
}
void init()
{memset(head,-1,sizeof(head));eid=0;
}
int main()
{//freopen("in.txt","r",stdin);int n,m,a,b,c;while(~scanf("%d%d",&m,&n)){init();while(m--){scanf("%d%d%d",&a,&b,&c);add(a,b,c);}printf("%d\n",isap(1,n,n));}return 0;
}