Pagini recente » Cod sursa (job #2246825) | Cod sursa (job #119167) | Cod sursa (job #2952086) | Cod sursa (job #249204) | Cod sursa (job #2967182)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 9999999
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
// O(N*M),N-nr varfuri, M-nr muchii
vector<vector<int>>la;
int capacitate[202][202];
int tata[202];
int n;
int BFS()
{
queue<pair<int,int>> q;
for(int i=0; i<=2*n+1; i++)
{
tata[i]=-1;
}
q.push({0,INF});
tata[0]=-2;
while(!q.empty())
{
int u=q.front().first;
int flow=q.front().second;
q.pop();
for(auto v:la[u])
{
if(tata[v]==-1 && capacitate[u][v]>0)
{
tata[v]=u;
int new_flow=min(flow,capacitate[u][v]);
if(v==2*n+1)
return new_flow;
q.push({v,new_flow});
}
}
}
return 0;
}
int calc()
{ int flow,maxflow=0;
while(flow=BFS())
{
maxflow+=flow;
int cur=2*n+1;
//revizuim flux lant
while(cur!=0)
{
int prev=tata[cur];
capacitate[cur][prev]+=flow;
capacitate[prev][cur]-=flow;
cur=prev;
}
}
return maxflow;
}
int main()
{
f>>n;
la.resize(2*n+2);
for(int i=1; i<=n; i++)
{
int x,y;
f>>x>>y;
la[0].push_back(i);// ad muchii cu cap x
la[i].push_back(0);
capacitate[0][i]=x;
capacitate[n+i][2*n+1]=y;//ad muchii cu cap y
la[n+i].push_back(2*n+1);
la[2*n+1].push_back(n+i);
for(int j=n+1; j<=2*n; j++)
{
if(j-i==n)// ad muc cu cap 1 si i!=j
continue;
capacitate[i][j]=1;
la[i].push_back(j);
la[j].push_back(i);
}
}
g<<calc()<<'\n';
for(int i=1; i<=n; i++)
for(int j=n+1; j<=2*n; j++)
if(capacitate[j][i]==1)
{
g<<i<<" "<<j-n<<'\n';
}
}