POJ 2391 Ombrophobic Bovines 网络流 建模

【题目大意】
给定一个无向图，点i处有Ai头牛，点i处的牛棚能容纳Bi头牛，求一个最短时间T使得在T时间内所有的牛都能进到某一牛棚里去。（1 <= N <= 200, 1 <= M <= 1500, 0 <= Ai <= 1000, 0 <= Bi <= 1000, 1 <= Dij <= 1,000,000,000）

 

一开始想拆点建图，0到x集合为汇，值为各个区域的牛数量， Y到终点连边，值为各个区域的容量，然后就是看怎么连x和y了

我一开始把可以连接的X和Y连起来，把可以互达的点在Y集合点那里连边，这样很麻烦，先跑一遍floyd把点到点的最短路求出来，然后直接X和Y集合可达即相连就行

二分结果，再建图，把在mid以内的X点对Y点连起来，跑最大流 判断结果即可

注意要用long long

一开始还没看清题意，一条路上可以同时走无数的牛，我一开始以为只能走一头，还敲MCMF去了。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define LL long long #define INF 1LL<<60 using namespace std; int f,p; const int maxn=500; struct Edge {int from,to,cap,flow; }; struct Dinic {vector<Edge>edges;vector<int> G[maxn];int vis[maxn];int cur[maxn];int d[maxn];void init(int n){edges.clear();for (int i=0; i<=n; i++){G[i].clear();}}void addedge(int from,int to,int cap){int m;edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){to,from,0,0});m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool bfs(int s,int t){memset(vis,0,sizeof vis);queue<int> q;q.push(s);d[s]=0;vis[s]=1;while (!q.empty()){int u=q.front();q.pop();for (int i=0; i<G[u].size(); i++){Edge& e=edges[G[u][i]];if (!vis[e.to] && e.cap>e.flow){vis[e.to]=1;d[e.to]=d[u]+1;q.push(e.to);}}}return vis[t];}int dfs(int x,int a,int t){if (x==t || a==0) return a;int flow=0,f;for (int& i=cur[x]; i<G[x].size(); i++){Edge& e=edges[G[x][i]];if (d[x]+1==d[e.to] && (f=dfs(e.to,min(a,e.cap-e.flow),t))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if (a==0) break;}}return flow;}int maxflow(int s,int t){int flow=0;while (bfs(s,t)){memset(cur,0,sizeof cur);flow+=dfs(s,100000000,t);}return flow;} } mcmf; int A[210],B[210]; LL path[210][210]; LL N; void floyd() {for (int i=1; i<=f; i++){for (int j=1; j<=f; j++){for (int k=1; k<=f; k++){if (j==k) continue;path[j][k]=min(path[j][k],path[j][i]+path[i][k]);N=max(N,path[j][k]);}}} } int main() {//freopen("POJ_2391.in","r",stdin);int a,b;LL c;while (scanf("%d%d",&f,&p)!=EOF){int cur=0;for (int i=1; i<=f; i++){scanf("%d%d",&A[i],&B[i]);cur+=A[i];for(int j=1; j<=f; j++) path[i][j]=INF;}for (int i=1; i<=p; i++){scanf("%d%d%lld",&a,&b,&c);path[a][b]=min(path[a][b],c);path[b][a]=min(path[b][a],c);}N=0;floyd();LL l,r,mid;l=1,r=N;//cout<<l<<" "<<r<<endl;LL ans=-1;while(l<r){mcmf.init(2*f+10);for (int i=1; i<=f; i++){mcmf.addedge(0,i,A[i]);mcmf.addedge(i,i+f,1<<30);}for (int i=1; i<=f; i++){mcmf.addedge(i+f,2*f+5,B[i]);}mid=(r+l)>>1;for (int i=1;i<=f;i++){for (int j=1;j<=f;j++){if (path[i][j]>mid || i==j) continue;mcmf.addedge(i,f+j,1<<30);}}int res=mcmf.maxflow(0,2*f+5);if (res>=cur){//cout<<res<<" "<<cur<<endl;//cout<<mid<<endl;ans=mid;r=mid;}else{l=mid+1;}}printf("%lld\n",ans);}return 0; }

　　

转载于:https://www.cnblogs.com/kkrisen/p/4013528.html

总结

以上是生活随笔为你收集整理的POJ 2391 Ombrophobic Bovines 网络流 建模的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。