P6768题解
一 解题算法
本题所用的算法是最短路、二分答案、网络最大流。此处最短路使用 Floyd 算法，最大流使用 Dinic 算法。
二 解题方法
建图：
网络流问题中建图（未知问题已知化）很重要，那么这题应该怎么建图呢？
先分析题目，题目要求最小时间，所以肯定符合二分答案的性质。先拆点，把牛棚和雨棚拆开，对于每次二分到的时间，如果某两点之间可以在这个时间内到达，则建起一条无限流量的边。然后建一个超级源点，到每个牛棚建一条边权为牛的数量的边，最后建一个超级汇点，每个雨棚连一条边权为雨棚容量的边到汇点。
“检测”函数：
众所周知，二分答案中有一个检测函数，那么这个函数怎么写呢？
每次跑一下最大流算法，如果流量大于总牛量则返回真，否则返回假。
三 参考代码
我做这到题的时候最大流写的不太熟练，是照着题解写的（并非抄，哪里借鉴代码中我会尽量注明），所以我的代码和一些题解会比较相似。这是完整代码：
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 4100
#define maxm 16000
#define inf 100000000000000000
using namespace std;
int n, m, cnt = 1, S, T;
ll ans = inf, sum;
int cow[maxn], house[maxn], head[maxn], nlast[maxn];
ll dis[maxn][maxn];
ll Min(ll x, ll y) { return x <= y ? x : y; }
struct edge
{
int to, next;
ll f;
}e[maxm << 3];
void add_edge(int f, int t, ll fl)
{
e[++cnt] = (edge){t, head[f], fl};
head[f] = cnt;
e[++cnt] = (edge){f, head[t], 0};
head[t] = cnt;
}
void input()
{
scanf("%d %d", &n, &m);
S = 2 * n + 1;
T = 2 * n + 2;
for (int i = 1; i <= n; ++i)
{
scanf("%d %d", &cow[i], &house[i]);
sum += (ll)cow[i];
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dis[i][j] = inf;
for (int i = 1; i <= n; ++i)
dis[i][i] = 0;
for (int i = 1; i <= m; ++i)
{
int from, to, Dis;
scanf("%d %d %d", &from, &to, &Dis);
dis[from][to] = Min(dis[from][to], Dis);
dis[to][from] = Min(dis[to][from], Dis);
//这里借鉴了题解
}
}
void init()
{
memset(head, 0, sizeof(head));
memset(nlast, 0, sizeof(nlast));
cnt = 1;
}
void Floyd()
{
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]);
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 1; j <= n; ++j)
// printf("%lld ", dis[i][j]);
// puts(" ");
// }
}
int dist[maxn];
bool vis[maxn];
bool bfs()
{
//bfs判断连通性，以及每一个点到终点的距离
memset(dist, 0, sizeof(dist));
memset(vis, 0, sizeof(vis));
queue <int> q;
vis[T] = true;
dist[T] = 1;
q.push(T);
while (!q.empty())
{
const int now = q.front();
//printf("%d ", now);
q.pop();
for (int i = head[now]; i; i = e[i].next)
{
const int to = e[i].to;
if (vis[to] == false && e[i ^ 1].f)
{//如果这条边的反向边还有残量，而且这个节点没被访问过
vis[to] = true;
dist[to] = dist[now] + 1;
q.push(to);
}
}
}
return vis[S];
}
ll Dinic(int x, ll f)
{
if (x == T) return f;
//如果这个点就是终点
ll now = f;
//now表示剩余流量
for (int i = nlast[x]; i; i = e[i].next)
{
const int to = e[i].to;
if (dist[to] == dist[x] - 1 && e[i].f)
{//Dinic的增广原则为先增广较短的增广路
const ll a = Dinic(to, Min(now, e[i].f));
//a记录增广路上所有边的最小值
e[i].f -= a;
//e[i ^ 1] 为反悔边，即可以退回流量
e[i ^ 1].f += a;
now -= a;
//增广出去剩余流量减少
if (now == 0) return f;
}
}
return f - now;
//返回这条路径能增广的量
}
ll maxflow()
{
ll now = 0;
while (bfs())
{
for (int i = 1; i <= n * 2 + 2; ++i)
nlast[i] = head[i];
now += Dinic(S, inf);
}
return now;
}
bool check(ll mid)
{
init();
for (int i = 1; i <= n; ++i)
{
add_edge(S, i, cow[i]);
add_edge(i + n, T, house[i]);
for (int j = 1; j <= n; ++j)
{
if (i == j || dis[i][j] <= mid)
add_edge(i, j + n, inf);
//这里借鉴了题解。
}
}
ll F = maxflow();
// printf("%lld\n", F);
return (F >= sum);
}
void search()
{
ll l = 0, r = inf;
while (l <= r)
{
ll mid = (l + r) >> 1;
//printf("%lld %d\n", mid, check(mid));
if (check(mid) == true)
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
}
void output()
{
if (ans == inf || ans == 0) printf("-1\n");
else printf("%lld", ans);
}
int main()
{
input();
Floyd();
search();
output();
return 0;
}管理员，求通过。