自动搬运

查看原文

来自洛谷，原作者为

	ker_xyxyxyx_xxs 最是人间留不住 朱颜辞镜花辞树

搬运于2025-08-24 21:37:18，当前版本为作者最后更新于2021-08-26 19:59:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2402 奶牛隐藏

二分答案 $+$ 网络流

建图：

1、源点 $\rightarrow$ 每块田，边权为牛的数量

2、每个牛棚 $\rightarrow$ 汇点，边权为牛棚最多能容纳的牛

3、对中间的边进行二分答案。具体操作如下。

使用 floyd 对两个点之间的最短距离预处理，对最小时间进行二分答案。如果在这个时间内可以从 $i$ 号田地走向 $j$ 号牛棚，就连一条边，容量为 $\infty$ ，最终检验最大流是否等于牛的数量即可。

一些易错点：

1、存在重边，邻接矩阵需要加上 $min$。

2、邻接矩阵每个点到自己的距离需要赋值为 $0$。

3、二分需要清空之前的数组。

Code

 # include <bits/stdc++.h>
using namespace std;
# define int long long
const int N = 1e6 + 5;
const int M = 2e6 + 5;
const int inf = 1e18; 
const int maxn = 200 + 5;

typedef struct {
	int x , y , z , next;
}Node;
Node edge[M];
int E = 1 , elast[N];
int S , T;

void add(int x , int y , int z) {
	E ++ , edge[E].x = x , edge[E].y = y , edge[E].z = z , edge[E].next = elast[x] , elast[x] = E;
}

int dis[N] , cnt[N];
void bfs(int start) {
    queue<int> q;
    q.push(start);
    dis[start] = 0;
    cnt[S] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = elast[cur] ; i ; i = edge[i].next) {
            int v = edge[i].y;
            if (dis[v] != -1) continue;
            dis[v] = dis[cur] + 1;
            q.push(v);
            cnt[dis[v]] ++;
        }
    }
}
int cur[N];
int dfs(int u , int flow) {
    if (u == T) return flow;
    int delta = 0;
    for (int i = cur[u] ; i ; i = edge[i].next) {
        cur[u] = i;
        int v = edge[i].y;
        if (edge[i].z > 0 && dis[u] == dis[v] + 1) {
            int temp = dfs(v , min(flow - delta , edge[i].z));
            edge[i].z -= temp;
            edge[i ^ 1].z += temp;
            delta += temp;
            if (delta == flow) return delta;
        }
    }
    if (dis[S] >= T + 1) return delta;
    cur[u] = elast[u];
    if (-- cnt[dis[u]] == 0) dis[S] = T + 1;
    cnt[++ dis[u]] ++;
    return delta;
}
int Isap() {
    int ans = 0;
    memset(cnt , 0 , sizeof cnt);
    memset(dis , -1 , sizeof dis);
    bfs(T);
    for (int i = 0 ; i <= T ; i ++) {
        cur[i] = elast[i];
    }
    while (dis[S] < T + 1) ans += dfs(S , inf);
    return ans;
}
int n , m;
int a[N] , b[N] , Dis[maxn][maxn];
void rebuild(int maxv) {
	for (int i = 1 ; i <= n ; i ++) {
    	add(S , i , a[i]) , add(i , S , 0);
    	add(n + i , T , b[i]) , add(T , n + i , 0);
    	for (int j = 1 ; j <= n ; j ++) {
    		if (Dis[i][j] <= maxv) add(i , n + j , inf) , add(n + j , i , 0);
		}
	}
}
void init() {
	memset(elast , 0 , sizeof elast);
	E = 1;
}
bool check(int cnt) {
	if (Isap() == cnt) return true;
	else return false;
}
int Cnt = 0;
signed main() {
	cin >> n >> m;
	for (int i = 1 ; i <= n ; i ++) {
		cin >> a[i] >> b[i];
		Cnt += a[i];
	}
	memset(Dis , 0x3f , sizeof Dis);
	for (int i = 1 ; i <= n ; i ++) Dis[i][i] = 0;
	for (int i = 1 ; i <= m ; i ++) {
		int x , y , z;
		cin >> x >> y >> z;
		Dis[x][y] = min(Dis[x][y] , z);
		Dis[y][x] = min(Dis[y][x] , z);
	}
	for (int k = 1 ; k <= n ; k ++) {
		for (int i = 1 ; i <= n ; i ++) {
			for (int j = 1 ; j <= n ; j ++) {
				Dis[i][j] = min(Dis[i][j] , Dis[i][k] + Dis[k][j]);
			}
		}
	}
    S = 0 , T = n << 1 | 1;
    int l = 0 , r = inf;
    int ans = 0;
	while (l <= r) {
    	int mid = (l + r) >> 1;
        init();
		rebuild(mid);
		bool flag = check(Cnt);
        if (!flag) l = mid + 1;
        else r = mid - 1 , ans = mid;
	}
	if (ans == 0) cout << "-1" << endl;
	else cout << ans << endl;
	return 0;
}