[模板] 杭电多校第一场
据说标题加模板浏览量 ++
1004 Vacation[思维]
只看始末状态.
假设车开到不影响杰瑞到达终点的地方就停止.
取一个时间的最大值就是答案.理由:
前面的车比后面快, 那影响答案的就是后面的到达时间; 如果前面的车比后面慢, 那么影响答案的就是前面的车的到达时间, 因为他们会接在一起, 然后同一时间出发和停止.
- #include<bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- ll n;
- ll l[100002], s[100002], v[100002];
- int main() {
- while (scanf("%lld", &n) != EOF) {
- for (ll i = 0; i <= n; ++i) {
- scanf("%lld", &l[i]);
- }
- for (ll i = 0; i <= n; ++i) {
- scanf("%lld", &s[i]);
- }
- for (ll i = 0; i <= n; ++i) {
- scanf("%lld", &v[i]);
- }
- double ans = s[0] * 1.0 / (v[0] * 1.0);
- ll tot = 0;
- for (ll i = 1; i <= n; ++i) {
- tot += l[i];
- ans = max(ans, ((tot + s[i]) * 1.0) / (v[i] * 1.0));
- }
- printf("%.10f\n", ans);
- }
- return 0;
- }
1005 Path[最短路 + 网络流]
求出所有的最短路径
然后复习一下最小割: https://www.cnblogs.com/smallocean/p/9509817.html
小心爆 int
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- template<class T>
- inline void read(T &res) {
- res = 0;
- T f = 1;
- char c;
- c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- res = res * 10 + c - '0';
- c = getchar();
- }
- res *= f;
- }
- const int maxn = 1e4 + 7;
- const int maxm = 2e4 + 7;
- const ll inf = 0x3f3f3f3f3f3f3f3f;
- struct Dinic {
- struct Edge {
- int next, to;
- ll f;
- } e[maxm];
- int head[maxn];
- ll dep[maxn], tol;
- ll ans;
- int cur[maxn];
- int src, sink, n;
- void add(int u, int v, int f) {
- tol++;
- e[tol].to = v;
- e[tol].next = head[u];
- e[tol].f = f;
- head[u] = tol;
- tol++;
- e[tol].to = u;
- e[tol].next = head[v];
- e[tol].f = 0;
- head[v] = tol;
- }
- bool bfs() {
- queue<int> q;
- for (register int i = 0; i <= n; ++i) dep[i] = -1;
- q.push(src);
- dep[src] = 0;
- while (!q.empty()) {
- int now = q.front();
- q.pop();
- for (register int i = head[now]; i; i = e[i].next) {
- if (dep[e[i].to] == -1 && e[i].f) {
- dep[e[i].to] = dep[now] + 1;
- if (e[i].to == sink)
- return true;
- q.push(e[i].to);
- }
- }
- }
- return false;
- }
- ll dfs(int x, ll maxx) {
- if (x == sink)
- return maxx;
- for (int &i = cur[x]; i; i = e[i].next) {
- if (dep[e[i].to] == dep[x] + 1 && e[i].f> 0) {
- ll flow = dfs(e[i].to, min(maxx, e[i].f));
- if (flow) {
- e[i].f -= flow;
- e[i ^ 1].f += flow;
- return flow;
- }
- }
- }
- return 0;
- }
- ll dinic(int s, int t) {
- ans = 0;
- this->src = s;
- this->sink = t;
- while (bfs()) {
- for (register int i = 0; i <= n; ++i)
- cur[i] = head[i];
- while (ll d = dfs(src, inf))
- ans += d;
- }
- return ans;
- }
- void init(int n) {
- this->n = n;
- for (int i = 0; i <= n; ++i)head[i] = 0;
- tol = 1;
- }
- } G;
- struct Dijk {
- ll dist[maxn];
- bool vis[maxn];
- struct qnode {
- int v;
- ll c;
- qnode(int _v = 0, ll _c = 0) : v(_v), c(_c) {}
- bool operator<(const qnode &r) const {
- return c> r.c;
- }
- };
- struct edge {
- int v;
- ll cost;
- edge(int _v = 0, ll _cost = 0) : v(_v), cost(_cost) {}
- };
- vector<edge> E[maxn];
- void add(int u, int v, int w) {
- E[u].emplace_back(edge(v, w));
- }
- void Dijkstra(int n, int start) {
- memset(vis, false, sizeof(vis));
- for (int i = 1; i <= n; ++i)dist[i] = inf;
- priority_queue<qnode> que;
- dist[start] = 0;
- que.push(qnode(start, 0));
- qnode tmp;
- while (!que.empty()) {
- tmp = que.top();
- que.pop();
- int u = tmp.v;
- if (vis[u])continue;
- vis[u] = true;
- for (int i = 0; i <E[u].size(); ++i) {
- int v = E[tmp.v][i].v;
- ll cost = E[u][i].cost;
- if (!vis[v] && dist[v]> dist[u] + cost) {
- dist[v] = dist[u] + cost;
- que.push(qnode(v, dist[v]));
- }
- }
- }
- }
- void init(int n) {
- for (int i = 0; i <= n; ++i) {
- E[i].clear();
- }
- }
- } a;
- struct node {
- int u, v;
- ll w;
- } s[maxn];
- int main() {
- int T;
- read(T);
- int n, m;
- int x, y, z;
- while (T--) {
- read(n);
- read(m);
- a.init(n);
- for (register int i = 0; i < m; ++i) {
- read(x);
- read(y);
- read(z);
- a.add(x, y, z);
- s[i].u = x, s[i].v = y, s[i].w = z;
- }
- a.Dijkstra(n, 1);
- G.init(n + 10);
- for (register int i = 0; i < m; ++i) {
- if (a.dist[s[i].v] - s[i].w == a.dist[s[i].u]) {
- G.add(s[i].u, s[i].v, s[i].w);
- }
- }
- printf("%lld\n", G.dinic(1, n));
- }
- return 0;
- }
[模板] 杭电多校第一场
来源: http://www.bubuko.com/infodetail-3131338.html