Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer. Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?
#include<bits/stdc++.h> usingnamespace std; /* TYPES */ #define int long long #define pii pair<int, int> #define F first #define S second #define vc vector #define vi vector<int> #define vii vector<pii> #define mii map<int, int> #define si set<int> /* UTILS */ #define rep(i, a, b) for (int i = a; i <= b; ++i) #define rev(i, a, b) for (int i = a; i >= b; --i) #define tomax(a, b) (a) = max((a), (b)) #define tomin(a, b) (a) = min((a), (b)) #define all(a) a.begin(), a.end() #define rall(a) (a).rbegin(), (a).rend() #define pob pop_back #define pb push_back #define eb emplace_back #define ins insert #define err(a) cerr << #a << ": " << a << "\n" #define sp << " " << #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int n, m; int adj[502][502]; bool vis[502];
booldfs(int rt, vector<int> &path, int threshold){ if (vis[rt]) returnfalse; vis[rt] = 1; if (rt == n) { path.push_back(rt); returntrue; } rep(i, 1, n) { if (adj[rt][i] < threshold) continue; if (dfs(i, path, threshold)) { path.push_back(rt); returntrue; } } returnfalse; }
signedmain(){ ios; cin >> n >> m; int threshold = 0; rep(i, 1, m) { int a, b, c; cin >> a >> b >> c; adj[a][b] += c; tomax(threshold, c); } int ans = 0; while (threshold > 0) { vector<int> path; memset(vis, 0, sizeof(vis)); if (dfs(1, path, threshold)) { reverse(path.begin(), path.end()); int k = path.size(); int flow = 1e9; rep (i, 0, k-2) tomin(flow, adj[path[i]][path[i + 1]]); ans += flow; rep (i, 0, k-2) { adj[path[i]][path[i + 1]] -= flow; adj[path[i + 1]][path[i]] += flow; } } else threshold >>= 1; } cout << ans << "\n"; return0; }
Kaaleppi has just robbed a bank and is now heading to the harbor. However, the police wants to stop him by closing some streets of the city. What is the minimum number of streets that should be closed so that there is no route between the bank and the harbor?
#include<bits/stdc++.h> usingnamespace std; /* TYPES */ #define int long long #define pii pair<int, int> #define F first #define S second #define vc vector #define vi vector<int> #define vii vector<pii> #define mii map<int, int> #define si set<int> /* UTILS */ #define rep(i, a, b) for (int i = a; i <= b; ++i) #define rev(i, a, b) for (int i = a; i >= b; --i) #define tomax(a, b) (a) = max((a), (b)) #define tomin(a, b) (a) = min((a), (b)) #define all(a) a.begin(), a.end() #define rall(a) (a).rbegin(), (a).rend() #define pob pop_back #define pb push_back #define eb emplace_back #define ins insert #define err(a) cerr << #a << ": " << a << "\n" #define sp << " " << #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
A game consists of n rooms and m teleporters. At the beginning of each day, you start in room 1 and you have to reach room n. You can use each teleporter at most once during the game. How many days can you play if you choose your routes optimally?
#include<bits/stdc++.h> usingnamespace std; /* TYPES */ #define int long long #define pii pair<int, int> #define F first #define S second #define vc vector #define vi vector<int> #define vii vector<pii> #define mii map<int, int> #define si set<int> /* UTILS */ #define rep(i, a, b) for (int i = a; i <= b; ++i) #define rev(i, a, b) for (int i = a; i >= b; --i) #define tomax(a, b) (a) = max((a), (b)) #define tomin(a, b) (a) = min((a), (b)) #define all(a) a.begin(), a.end() #define rall(a) (a).rbegin(), (a).rend() #define pob pop_back #define pb push_back #define eb emplace_back #define ins insert #define err(a) cerr << #a << ": " << a << "\n" #define sp << " " << #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int n, m, ans = 0; int g[502][502]; bool vis[502]; vi go[502];
There are n boys and m girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are k potential pairs. Your task is to find out the maximum number of dance pairs and show how this number can be achieved.
#include<bits/stdc++.h> usingnamespace std; /* TYPES */ #define int long long #define pii pair<int, int> #define F first #define S second #define vc vector #define vi vector<int> #define vii vector<pii> #define mii map<int, int> #define si set<int> /* UTILS */ #define rep(i, a, b) for (int i = a; i <= b; ++i) #define rev(i, a, b) for (int i = a; i >= b; --i) #define tomax(a, b) (a) = max((a), (b)) #define tomin(a, b) (a) = min((a), (b)) #define all(a) a.begin(), a.end() #define rall(a) (a).rbegin(), (a).rend() #define pob pop_back #define pb push_back #define eb emplace_back #define ins insert #define err(a) cerr << #a << ": " << a << "\n" #define sp << " " << #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int n, m, k, ans; int g[1003][1003]; bool vis[1003]; vi go[1003];