Pagini recente » Cod sursa (job #3167213) | Cod sursa (job #571223) | Cod sursa (job #2239757) | Cod sursa (job #1078922) | Cod sursa (job #2680760)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define Dim 1000000000
#define N 210
using namespace std;
vector <int> G[N];
queue <int> q;
int n,m,C[N][N],pred[N],f[N][N];
int source,sink;
bool viz[N];
void read()
{
int i,x,y;
freopen("harta.in","r",stdin);
scanf("%d",&n);
source=0;
sink=2*n+1;
for(i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
G[source].emplace_back(i);
G[i].emplace_back(source);
C[source][i]=x;
G[i+n].emplace_back(sink);
G[sink].emplace_back(i+n);
C[i+n][sink]=y;
}
for(int i=1;i<=n;++i)
for(int j=n+1;j<=2*n;++j){
if(i+n != j){
G[i].emplace_back(j);
G[j].emplace_back(i);
C[i][j] = 1;
}
}
}
bool bfs()
{
memset(viz,0,sizeof(viz));
q.push(source);
viz[source] = 1;
while(!q.empty())
{
int nod = q.front();
q.pop();
if(nod == sink)
continue;
for(auto& i:G[nod])
{
if(viz[i] || f[nod][i] == C[nod][i])
continue;
viz[i] = 1;
q.push(i);
pred[i] = nod;
}
}
return viz[sink];
}
int Edmond()
{
int flow,i,f_min,nod,pj;
for(flow = 0; bfs() ;){
for(auto& i:G[sink])
{
if(!viz[i] || f[i][sink] == C[i][sink])
continue;
pred[sink] = i;
nod = sink;
f_min = Dim;
while(nod != source)
{
f_min = min(f_min, C[pred[nod]][nod] - f[pred[nod]][nod]);
nod = pred[nod];
}
if(!f_min)
continue;
//actualizare
nod = sink;
while(nod != source)
{
f[pred[nod]][nod] += f_min;
f[nod][pred[nod]] -= f_min;
nod = pred[nod];
}
flow += f_min;
}
}
return flow;
}
int main()
{
read();
freopen("harta.out","w",stdout);
cout<<Edmond()<<'\n';
for(int i=1;i<=n;++i)
for(int j=n+1;j<=2*n;++j){
if(i+n != j && f[i][j] == C[i][j])
cout<<i<<' '<<j-n<<'\n';
}
}