Pagini recente » Cod sursa (job #239070) | Cod sursa (job #1647688) | Cod sursa (job #2916702) | Cod sursa (job #2531558) | Cod sursa (job #1250742)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> v[105];
queue <int> q;
int n,use[105],ant[105],fol[105][105],c[105][105],s,t,x1[505],x2[505],k;
int BFS()
{ int i,nod,nod2;
memset(use,0,sizeof(use));
memset(ant,0,sizeof(ant));
q.push(s); use[s]=1;
while(!q.empty())
{ nod=q.front(); q.pop();
if (nod==t) continue;
for(i=0;i<v[nod].size();i++)
{ nod2=v[nod][i];
if (!use[nod2] && fol[nod][nod2]<c[nod][nod2])
{ q.push(nod2);
use[nod2]=1;
ant[nod2]=nod;
}
}
}
return use[t]>0;
}
void Flux()
{ int i,x,j,n1,n2,res;
while(BFS())
{
for(i=0;i<v[t].size();i++)
{ x=v[t][i]; res=c[x][t]-fol[x][t];
while(ant[x])
{ n1=ant[x]; n2=x;
res=min(res,c[n1][n2]-fol[n1][n2]);
x=ant[x];
}
x=v[t][i]; fol[x][t]+=res; fol[t][x]-=res;
while(ant[x])
{ n1=ant[x]; n2=x;
fol[n1][n2]+=res;
fol[n2][n1]-=res;
x=ant[x];
}
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (fol[i][j+n]>0)
{k++; x1[k]=i; x2[k]=j; }
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<x1[i]<<" "<<x2[i]<<"\n";
}
int main()
{ int i,j,x,y;
f>>n;
s=2*n+1; t=2*n+2;
for(i=1;i<=n;i++)
{ f>>x>>y;
v[s].push_back(i); v[i].push_back(s); c[s][i]+=x;
v[i+n].push_back(t); v[t].push_back(i+n); c[i+n][t]+=y;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (i!=j)
{v[i].push_back(j+n); v[j+n].push_back(i); c[i][j+n]+=1;}
Flux();
return 0;
}