本文共 1670 字，大约阅读时间需要 5 分钟。
求从电站->调度站->消费者的最大流，给出一些边上的容量。和电站和消费者能够输入和输出的最大量。
加入一个超级源点和汇点，建边跑模板就能够了。
两个模板逗能够。
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f#define eps 1e-6#define ll __int64const int maxn=110;using namespace std;int n,m,np,nc,s,t;int level[maxn],c[maxn][maxn];bool makelevel(){ memset(level,0,sizeof level); level[s]=1; int q[maxn]; int fro=0,iq=0; q[iq++]=s; int i,v; while(fro!=iq) { v=q[fro++]; for(i=1;i<=n+2;i++)//注意点的编号 { if(!level[i]&&c[v][i]) { level[i]=level[v]+1; q[iq++]=i; } } } if(!level[t]) return 0; return 1;}int dfs(int now,int maxf){ if(now==t) return maxf; int ret=0; for(int i=1;maxf&&i<=n+2;i++)//注意点的编号 { if(c[now][i]&&level[now]+1==level[i]) { int tmp=dfs(i,min(maxf,c[now][i])); c[now][i]-=tmp; c[i][now]+=tmp; ret+=tmp; maxf-=tmp; } } return ret;}int dinic(){ int ans=0; while(makelevel()) ans+=dfs(s,inf); return ans;}/*int c[maxn][maxn],p[maxn];bool bfs(){ queue q; bool vis[maxn]; memset(vis,0,sizeof vis); memset(p,-1,sizeof p); q.push(s); vis[s]=1; while(!q.empty()) { int e=q.front(); if(e==t) return 1; q.pop(); for(int i=1;i<=n+2;i++)//注意点的范围 { if(c[e][i]&&!vis[i]) { vis[i]=1; p[i]=e; q.push(i); } } } return 0;}int ek(){ int u,ans=0,mn; while(bfs()) { mn=inf; u=t; while(p[u]!=-1) { mn=min(mn,c[p[u]][u]); u=p[u]; } ans+=mn; u=t; while(p[u]!=-1) { c[p[u]][u]-=mn; c[u][p[u]]+=mn; u=p[u]; } } return ans;}*/int main(){ int i,a,b,cc; while(~scanf("%d%d%d%d",&n,&np,&nc,&m)) { s=n+1,t=n+2; memset(c,0,sizeof c); for(i=0;i
转载于:https://www.cnblogs.com/blfshiye/p/5093080.html