校内模拟赛 Attack's Fond Of LeTri

Attack's Fond Of LeTri

题意：

　　n个房子m条路径边的无向图，每个房子可以最终容纳b个人，初始有a个人，中途超过可以超过b个人，每条边有一个长度，经过一条边的时间花费为边的长度。求所有人都进入房子的最小时间。如果不能容纳所有人，输出最少多少人无法进入房子。

分析：

　　注意图不一定联通！！！

　　首先Floyd一遍，求出任意两点之间的距离，二分一个答案，然后拆点建二分图，S想每个点连a的容量，另一个点向T连b的容量，对于两个点a,b，如果dis[a][b]<=二分的这个数，就加入一条左边到右边的边，容量为inf。满流即可。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cctype>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#define fore(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , INF = 1e9;

struct Edge { int to, nxt, cap; } e[];

int head[N], q[], a[N], b[N], dis[N], cur[N];

int En = , S, T, n;

LL d[][], Sum;

inline void add_edge(int u,int v,int f) {

    ++En; e[En].to = v, e[En].nxt = head[u], e[En].cap = f; head[u] = En;

    ++En; e[En].to = u, e[En].nxt = head[v], e[En].cap = ; head[v] = En;

}

bool bfs() {

    for (int i = ; i <= T; ++i) dis[i] = -, cur[i] = head[i];

    int L = , R = ; q[++R] = S; dis[S] = ;

    while (L <= R) {

        int u = q[L ++];

        fore(i, u, v)

            if (dis[v] == - && e[i].cap > ) {

                dis[v] = dis[u] + ;

                if (v == T) return true;

                q[++R] = v;

            }

    }

    return false;

}

int dfs(int u,int flow) {

    if (u == T) return flow;

    int used = , tmp;

    for (int &i = cur[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (dis[v] == dis[u] +  && e[i].cap > ) {

            tmp = dfs(v, min(e[i].cap, flow - used));

            if (tmp > ) {

                e[i].cap -= tmp, e[i ^ ].cap += tmp; used += tmp;

                if (used == flow) break;

            }

        }

    }

    if (flow != used) dis[u] = -;

    return used;

}

bool dinic(LL x, bool flag) {

    S = , T = n + n + , En = ;

    memset(head, , sizeof(head));

    for (int i = ; i <= n; ++i) add_edge(S, i, a[i]), add_edge(i + n, T, b[i]);

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= n; ++j)

            if (d[i][j] <= x) add_edge(i, j + n, INF);

    LL ans = ;

    while (bfs()) ans += dfs(S, INF);

    if (flag && ans != Sum) {

        cout << "NO\n" << Sum - ans; exit();

    }

    return ans == Sum;

}

void solve(int m) {

    for (int i = ; i <= n; ++i) Sum += a[i];

//    memset(d, 0x3f, sizeof(d));

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= n; ++j) d[i][j] = 1e18;

    for (int i = ; i <= n; ++i) d[i][i] = ;

    for (int i = ; i <= m; ++i) {

        int u = read(), v = read(), w = read();

        d[u][v] = min(d[u][v], (LL)w);

        d[v][u] = min(d[v][u], (LL)w);

    }

    for (int k = ; k <= n; ++k)

        for (int i = ; i <= n; ++i)

            for (int j = ; j <= n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    LL L = 1e18, R = , ans = ;

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= n; ++j) if (d[i][j] != 1e18) L = min(L, d[i][j]), R = max(R, d[i][j]); // 注意要有dis[i][j]!=1e18???

    dinic(R, );

    while (L <= R) {

        LL mid = (L + R) >> ;

        if (dinic(mid, )) R = mid - , ans = mid;

        else L = mid + ;

    }

    cout << "YES\n" << ans << "\n";

}

int main() {

    n = read();int m = read();

    for (int i = ; i <= n; ++i) a[i] = read(), b[i] = read();

    solve(m);

    return ;

}