1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 444 #define INF 987654321987654321 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define all5 array<ll,5> #define vall5 vector<all5> #define vll vector<ll> #define vs vector<string> #define usll unordered_set<ll> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a) using namespace std;
ll source = 404, sink = 405; ll cap[MAX_N][MAX_N], cost[MAX_N][MAX_N], flo[MAX_N][MAX_N], path[MAX_N]; vll adj[MAX_N];
void connect(ll u, ll v, ll capacity, ll weight) { adj[u].push_back(v); adj[v].push_back(u);
cap[u][v] += capacity;
cost[u][v] += weight; cost[v][u] += -weight; }
bool bfs(ll u, ll v) { vll w(MAX_N, INF); bool inc[MAX_N]; memset(path, 0, sizeof path); memset(inc, 0, sizeof inc); queue<ll> q; q.push(u); w[u] = 0;
while(!q.empty()) { auto n = q.front(); q.pop(); inc[n] = false; for(auto& m : adj[n]) { if(cap[n][m] - flo[n][m] > 0 and w[n] + cost[n][m] < w[m]) { w[m] = w[n] + cost[n][m]; path[m] = n; if(!inc[m]) { inc[m] = true; q.push(m); } } } }
return path[v] != 0; }
pll solve() { ll res = 0, flow = 0; while(bfs(source, sink)) { ll v = sink, mi = INF; while(source != v) { ll u = path[v]; mi = min(mi, cap[u][v] - flo[u][v]); v = u; } v = sink; flow += mi; while(source != v) { ll u = path[v]; res += mi * cost[u][v]; flo[u][v] += mi; flo[v][u] -= mi; v = u; } } return {flow, res}; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(6); ll n, m, u, v, w; cin>>n>>m;
for(ll i = 1, gap = 200; i <= m; i++) { cin>>u>>v>>w; connect(u,v + gap,1,w); }
for(ll i = 1, gap = 200; i <= n; i++) { connect(source, i, 1, 0); connect(i + gap, sink, 1, 0); }
auto [flow, res] = solve(); cout<<(flow == n)<<'\n'; if(flow != n) exit(0); cout<<res<<'\n'; for(ll u = 1; u <= n; u++) { for(auto& v : adj[u]) { if(flo[u][v] and v != source and v != sink) { cout << u << ' ' << v - 200 << '\n'; } } } return 0; }
|