学步园

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;
}

isap

int get_flow(int u, int flow)
{
    if(u==T || flow==0)return flow;
    int res=0, f;
    for(int i=head[u]; ~i; i=edge[i].next) {
        int &v = edge[i].to;
        if(d[u]>d[v] && (f=get_flow(v,min(flow,edge[i].cap)))>0) {
            edge[i].cap -= f;
            edge[i^1].cap += f;
            res += f;
            flow -= f;
            if(flow==0) return res;
        }
    }
    if(!(--gap[d[u]]))d[S]=cnt+2;
    gap[++d[u]]++;
    return res;
}

int isap()
{
    int flow = 0;
    memset(gap, 0, sizeof gap );
    memset(d, 0, sizeof d );
    cnt = T-S+1;//顶点数
    gap[0] = cnt;
    while(d[S]<cnt) flow += get_flow(S, inf);
    return flow;
}