Pagini recente » Cod sursa (job #1356955) | Cod sursa (job #2962462)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> lista;
int cap[205][205],a,b,i,j,u;
vector<int> tata;
int n,s,t;
bool bfs()
{
vector<bool> viz(2*n+1);
queue<int> que;
que.push(s);
viz[s] = true;
tata[s] = -1;
while(!que.empty())
{
u = que.front();
que.pop();
for(auto v: lista[u])
{
if(viz[v]==false && cap[u][v]!=0)
{
tata[v] = u;
if(v == t)
return true;
viz[v] = true;
que.push(v);
}
}
}
return false;
}
int EdmondsKarp()
{
long maxf = 0;
while(bfs()==true)
{
int u, v, drum = INT_MAX;
v=t;
while(v != s)
{
u = tata[v];
if(cap[u][v] < drum)
drum = cap[u][v];
v = tata[v];
}
v=t;
while(v != s)
{
u = tata[v];
cap[u][v] -= drum;
cap[v][u] += drum;
v = tata[v];
}
maxf += drum;
}
return maxf;
}
int main()
{
f>>n;
lista.resize(201);
tata.resize(2*n+1);
for( i=1; i<=n; i++)
for( j=1; j<=n; j++)
{
if(i!=j)
{
lista[i].push_back(j+n);
lista[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;
lista[s].push_back(i);
lista[i].push_back(s);
cap[s][i]=a;
lista[i+n].push_back(t);
lista[t].push_back(i+n);
cap[i+n][t]=b;
}
g << EdmondsKarp()<<"\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";
}
return 0;
}