Pagini recente » Cod sursa (job #3135002) | Cod sursa (job #1894021) | Cod sursa (job #1231712) | Rating Spiridusul Vesel (spiridusulvesel) | Cod sursa (job #2966055)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> LA;
vector<int> F;
int cap[201][201];
int n,s,t;
bool bfs()
{
vector<bool> viz(2*n+1);
queue<int> q;
q.push(s);
viz[s] = true;
F[s] = -1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v: LA[u]) {
if(viz[v]==false && cap[u][v]!=0) {
F[v] = u;
if(v == t)
return true;
viz[v] = true;
q.push(v);
}
}
}
return false;
}
int ekarp()
{
long max_flow = 0;
while(bfs()==true) {
int u, v, path_flow = INT_MAX;
v=t;
while(v!=s) {
u = F[v];
if(cap[u][v] < path_flow)
path_flow = cap[u][v];
v = F[v];
}
v=t;
while(v!=s) {
u = F[v];
cap[u][v] -= path_flow;
cap[v][u] += path_flow;
v = F[v];
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
ifstream f("harta.in");
ofstream g("harta.out");
f>>n;
int a,b,i,j;
LA.resize(201);
F.resize(2*n+1);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
if(i!=j) {
LA[i].push_back(j+n);
LA[j+n].push_back(i);
cap[i][j+n]=1;
}
}
s=0;
t=2*n+1;
for(i=1; i<=n; i++) {
f>>a>>b;
LA[s].push_back(i);
LA[i].push_back(s);
cap[s][i]=a;
LA[i+n].push_back(t);
LA[t].push_back(i+n);
cap[i+n][t]=b;
}
g<<ekarp()<<"\n";
for(i=1; i<=n; i++)
for(j=n+1; j<=2*n; j++) {
if(cap[j][i]==1)
g<<i<<" "<<j-n<<"\n";
}
f.close(); g.close();
return 0;
}