本文主要是介绍【Gym - 101908G Gasoline】【二分答案】【网络流】【边之间有时间，求把油站填满的最小时间】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://codeforces.com/gym/101908/problem/G
【题意】：边之间有时间，求把油站填满的最小时间
【思路】很容易想到是网络流，关键是最小时间。我们直接二分最小时间，然后如果某条边的时间比二分值小，那么就连边。然后跑最大流，看看最大流等不等于油站和，等于的话证明可行。
【代码】由于边比较多，使用dinic算法
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n, m, k;
int sum, x[1500], y[1500], u[20020], v[20020], w[20020];
int head[2020], vis[2200], dis[2100], cur[2100], cnt;struct node{int to, flow, next;
}edge[50000];void add(int u, int v, int w){edge[cnt].to = v;edge[cnt].flow = w;edge[cnt].next = head[u];head[u] = cnt++;edge[cnt].to = u;edge[cnt].flow = 0;edge[cnt].next = head[v];head[v] = cnt++;
}int bfs(int s, int t){memset(vis, 0x7f, sizeof(vis));queue<int>q;q.push(s);vis[s] = 0;while (!q.empty()){s = q.front();q.pop();for (int i = head[s]; i != -1; i = edge[i].next){int to = edge[i].to;int flow = edge[i].flow;if (flow&&vis[to]>0x7f){vis[to] = vis[s] + 1;q.push(to);}}}if (vis[t]<inf)return 1;else return 0;
}int dfs(int s, int t, int limit){if (!limit || s == t)return limit;int flow = 0, f;for (int i = cur[s]; i != -1; i = edge[i].next){cur[s] = i;if (vis[edge[i].to] == vis[s] + 1){f = dfs(edge[i].to, t, min(limit, edge[i].flow));flow += f;limit -= f;edge[i].flow -= f;edge[i ^ 1].flow += f;if (!limit)break;}}return flow;
}int dinic(int s, int t){int ans = 0;while (bfs(s, t)){memcpy(cur, head, sizeof(head));ans += dfs(s, t, inf);}return ans;
}int build(int mid){memset(head, -1, sizeof(head));cnt = 0;for (int i = 1; i <= m; i++)//源点add(0, i, y[i]);for (int i = 1; i <= n; i++)//汇点add(i + m, m + n + 1, x[i]);for (int i = 1; i <= k; i++){if (w[i] <= mid)add(v[i], u[i] + m, inf);}int t = dinic(0, m + n + 1);if (t == sum)return 1;else return 0;
}int main(){while (~scanf("%d%d%d", &n, &m, &k)) {sum = 0;for (int i = 1; i <= n; i++) {scanf("%d", &x[i]);sum += x[i];}for (int i = 1; i <= m; i++) {scanf("%d", &y[i]);}for (int i = 1; i <= k; i++) {scanf("%d%d%d", &u[i], &v[i], &w[i]);}int l = 1, r = 1000000, ans = -1;while (l <= r) {int mid = (l + r) / 2;if (build(mid)) {r = mid - 1;ans = mid;}else l = mid + 1;}printf("%d\n", ans);}
}
这篇关于【Gym - 101908G Gasoline】【二分答案】【网络流】【边之间有时间，求把油站填满的最小时间】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
