首页 > 代码库 > POJ 2391 Ombrophobic Bovines 网络流 建模
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<<60using 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;}
POJ 2391 Ombrophobic Bovines 网络流 建模
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。