P2402 奶牛隐藏

· · 题解

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