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;

}