听说二分答案与网络流更配哦

懵逼的 题目

传送至 Luogu

扯淡的 题解

Emmmmm…补去年的坑…

当时SLR(Orzzzzz)拉我做这个题…我直接费用流挑最大费用…WAWAWAWAWA….

Emmmmm…现在一看还是挺显然的二分答案的…

floyd求出两两点之间的最短距离, 拆点, 把每一片田地都拆成$A, B$两个, 二分答案ans, 枚举所有点对, 如果$dis(x,\, y) \le ans$, 就从$A_x$向$B_y$连一条容量为INF的边, 然后从$S$向所有的$A_i$连边, 容量为节点$i$初始的奶牛数量, 从每一个$B_i$向$T$连边, 容量为节点$i$可以容纳的奶牛数量, 然后判断最大流是否等于初始所有奶牛的和即可

以奇怪的姿势WA了好几发…

  • 要用LL, 结果输出忘记改成"%lld"
  • dinic的bfs(), 忘记dis[s] = 1

深感药丸

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXG (200 + 5)
#define INF (10000000000000ll)
#define bh(a) ((a) + 500)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define LL long long
#define int LL 
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from, to, next, cap, flow;
    edg() {}
    edg(int fr, int dqt, int ne, int ca): from(fr), to(dqt), next(ne), cap(ca), flow(0) {}
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN], ncow[MAXN], nspa[MAXN], n, m, gx[MAXG][MAXG];
void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap);
    g[from] = cntb;
}
inline int min(const int x, const int y)
{ return (x < y ? x : y); }
int dinic(int dq, int maxf)
{
    if (dq == t || !maxf)
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
            maxf -= zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            re += zl;
        }
    return re;
}
int bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1; // 好像忘记写这个了... 
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
            if (b[i].cap > b[i].flow && !dis[b[i].to])
                dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
    }
    return dis[t];
}
int solve()
{
    int re = 0;
    while (bfs())
        re += dinic(s, INF);
    return re;
}
void floyed()
{
    for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (gx[i][k] < INF && gx[k][j] < INF && i != j && j != k && i != k)
            gx[i][j] = min(gx[i][j], gx[i][k] + gx[k][j]);
}
void init(int cap)
{
    memset(g, 0, sizeof(g));
    cntb = 0;
    for (int i = 1; i <= n; i++)
    {
        adn(s, i, ncow[i]);
        adn(i, s, 0);

        adn(bh(i), t, nspa[i]);
        adn(t, bh(i), 0);
        for (int j = 1; j <= n; j++)
            if (gx[i][j] <= cap)
            {
                adn(i, bh(j), INF);
                adn(bh(j), i, 0);
            }
    }
}
int ef()
{
    int le = 0, ri = INF, ans = -1;
    while (le < ri)
    {
        int mi = (le + ri) >> 1;
        init(mi);
        if (solve() == ncow[0])
            ans = mi, ri = mi;
        else
            le = mi + 1;
    }
    return ans;
}
main()
{
    freopen("in.in", "r", stdin);
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &ncow[i], &nspa[i]), ncow[0] += ncow[i];
    memset(gx, 0x7f, sizeof(gx));
    for (int i = 1; i <= n; i++)    gx[i][i] = 0;

    for (int i = 1; i <= m; i++)
    {
        int srx, sry, srz;
        scanf("%lld%lld%lld", &srx, &sry, &srz);
        gx[srx][sry] = gx[sry][srx] = min(srz, gx[sry][srx]);
    }
    floyed();
    printf("%lld", ef());
    return 0;    
}

/*
3 4 
7 2 
0 4 
2 6 
1 2 40 
3 2 70 
2 3 90 
1 3 120
*/

By 沙茶的 Cansult