Pagini recente » Cod sursa (job #361049) | Cod sursa (job #3340032) | Cod sursa (job #564284) | Cod sursa (job #2238154) | Cod sursa (job #3336807)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, m, e, N;
vector<vector<int>>Adj;
vector<vector<int>>Adj_rev;
vector<vector<long>>flow;
vector<vector<long>>capacity;
vector<int>parent;
vector<int>vis;
vector<int>din;
vector<int>dout;
bool bfs(int s, int t) {
parent.assign(N, 0);
vis.assign(N, 0);
queue<int>q;
q.push(s);
vis[s]=1;
while (!q.empty()) {
int u=q.front();
q.pop();
for (int &v:Adj[u]) {
if (vis[v]==0 && capacity[u][v] - flow[u][v] > 0 ) {
parent[v]=u;
if (v == t)
return 1;
q.push(v);
vis[v]=1;
}
}
for (int& v:Adj_rev[u]) {
if (vis[v]==0 && flow[v][u] > 0 ) {
parent[v]=-u;
if (v == t)
return 1;
q.push(v);
vis[v]=1;
}
}
}
return 0;
}
long EdmondsKarp(int s, int t) {
long maxflow=0;
while (bfs(s, t)) {
int node = t;
long ip = LONG_MAX;
while (node!=s) {
if (parent[node] > 0) {
ip = min(ip, capacity[parent[node]][node] - flow[parent[node]][node]);
node=parent[node];
}
else {
ip = min(ip, flow[node][-parent[node]]);
node=-parent[node];
}
}
node = t;
while (node!=s) {
if (parent[node] > 0) {
flow[parent[node]][node] += ip;
node=parent[node];
}
else {
flow[node][-parent[node]]-=ip;
node=-parent[node];
}
}
maxflow+=ip;
}
return maxflow;
}
int main() {
fin>>n;
N=n+n+3;
Adj.resize(N);
Adj_rev.resize(N);
flow.resize(N);
capacity.resize(N);
din.assign(n+1, 0);
dout.assign(n+1, 0);
for (int i=0;i<=n+n+2;i++) {
flow[i].assign(N, 0);
capacity[i].assign(N, 0);
}
for (int i=1;i<=n;i++)
fin>>dout[i]>>din[i];
int s=n+n+1, t=n+n+2;
for (int i=1;i<=n;i++) {
Adj[s].push_back(i);
Adj_rev[i].push_back(s);
capacity[s][i] = dout[i];
}
for (int i=n+1;i<=n+n;i++){
Adj[i].push_back(t);
Adj_rev[t].push_back(i);
capacity[i][t] = din[i-n];
}
for (int i=1;i<=n;i++)
for (int j=n+1;j<=n+n;j++) {
if (j - n == i) continue;
Adj[i].push_back(j);
Adj_rev[j].push_back(i);
capacity[i][j]=1;
}
int nr_drumuri=EdmondsKarp(s, t);
fout<<nr_drumuri<<'\n';
for (int nod1 = 1; nod1 <= n; nod1++) {
for (int nod2 = n+1; nod2 <= 2*n; nod2++) {
if (flow[nod1][nod2] == 1) {
fout << nod1 << " " << (nod2 - n) << "\n";
}
}
}
return 0;
}