Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
using namespace std; const int maxn = 100; int n, m; int graph[maxn][maxn]; bool bfs(vector
> & r_graph, int S, int E, vector
& parent) { vector
visited(n + 1, false); visited[S] = true; queue
q; q.push(S); parent[S] = -1; while(!q.empty()) { int node = q.front(); q.pop(); for(int i = 0; i < n; i++) { if(!visited[i] and r_graph[node][i] > 0) { if(i == E) { parent[i] = node; return true; } q.push(i); visited[i] = true; parent[i] = node; } } } return false; } int max_flow(int S, int E) { vector
> r_graph(n, vector
(n, 0)); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { r_graph[i][j] = graph[i][j]; } } vector
parent(n); int res = 0; while(bfs(r_graph, S, E, parent)) { int path_flow = 2e9; for(int i = E; i != S; i = parent[i]) { path_flow = min(path_flow, r_graph[parent[i]][i]); } for(int i = E; i != S; i = parent[i]) { r_graph[parent[i]][i] -= path_flow; r_graph[i][parent[i]] += path_flow; } res += path_flow; } return res; } int main() { int m; cin >> m; n = 26; for(int i = 0; i < m; i++) { char a, b; cin >> a >> b; int c; cin >> c; graph[a - 'A'][b - 'A'] = c; } cout << "DA" << endl; cout << max_flow(('S' - 'A'), ('T' - 'A')) << endl; return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)