首页 > 代码库 > poj 2391 Ombrophobic Bovines, 最大流, 拆点, 二分, dinic
poj 2391 Ombrophobic Bovines, 最大流, 拆点, 二分, dinic
poj 2391 Ombrophobic Bovines,
最大流, 拆点, 二分
dinic
/* * Author: yew1eb * Created Time: 2014年10月31日 星期五 15时39分22秒 * File Name: poj2391.cpp */ #include <ctime> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; const int inf = 1e9; const ll INF = 1e18; const double eps = 1e-8; const double pi = acos(-1.0); const int maxn = 600; const int maxm = 100000; struct Edge{ int to, next; int cap; Edge(){} Edge(int nt, int t, int cp):next(nt),to(t),cap(cp){} }edge[maxm]; int head[maxn], tot; int n, m, S, T; void init(){ tot = 0; memset(head, -1, sizeof head ); } void add(int u, int v, int c){ edge[tot] = Edge(head[u], v, c); head[u] = tot++; edge[tot] = Edge(head[v], u, 0); head[v] = tot++; } int d[maxn]; bool vis[maxn]; bool bfs(){ queue<int> q; q.push(S); memset(vis, 0, sizeof vis ); vis[S] = 1; d[S] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(int i=head[u]; ~i; i=edge[i].next){ int &v = edge[i].to; if(!vis[v] && edge[i].cap>0){ vis[v] = 1; d[v] = d[u] + 1; q.push(v); } } } return vis[T]; } int dfs(int u, int a){ if(u==T||a==0) return a; int flow = 0, f; for(int i=head[u];~i; i=edge[i].next){ int &v = edge[i].to; if(d[u]+1==d[v]&&(f=dfs(v,min(a,edge[i].cap)))>0){ edge[i].cap -= f; edge[i^1].cap += f; flow += f; a -= f; if(a==0) break; } } return flow; } int dinic(){ int flow = 0; while(bfs()){ flow += dfs(S, inf); } return flow; } ll g[maxn][maxn]; void floyd(){ for(int k=1; k<=n; ++k) for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j){ g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } int a[maxn], b[maxn]; void create_graph(ll x){ init(); for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) if(g[i][j]<=x) add(i,j+n, inf); for(int i=1; i<=n; ++i){ add(S, i, a[i]); add(i+n, T, b[i]); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.cpp", "w", stdout); #endif // ONLINE_JUDGE scanf("%d%d", &n, &m); int u, v, c; S = 0, T = 2*n+2; int sum = 0; for(int i=1; i<=n; ++i){ scanf("%d%d", &a[i], &b[i]); sum += a[i]; } for(int i=1; i<=n; ++i) { g[i][i] = 0; for(int j=i+1; j<=n; ++j) g[i][j] = g[j][i] = INF; } for(int i=1; i<=m; ++i){ scanf("%d%d%d", &u, &v, &c); if(g[u][v]>c) g[u][v] = g[v][u] = c; } floyd(); //bsearch ll l = 0, r = 0, mid, ans = -1; for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) if(g[i][j]<INF) r = max(r, g[i][j]); while(l<=r){ mid = (l+r)>>1; create_graph(mid); int flow = dinic(); if(flow == sum){ ans = mid; r = mid - 1; }else l = mid + 1; } cout<<ans<<endl; return 0; }
poj 2391 Ombrophobic Bovines, 最大流, 拆点, 二分, dinic
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。