Pagini recente » Cod sursa (job #184045) | Cod sursa (job #202288) | Cod sursa (job #1031118) | Cod sursa (job #2951276) | Cod sursa (job #1204751)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int INF = 1000000000;
int n,i,k,nod,p,u,x,y,j,Min;
int q[200],C[200][200],F[200][200],T[200],sol[20000][2];
bool viz[1000];
vector<int> L[200];
vector<int>::iterator it;
inline int minim(int a, int b) {
return a<b ? a : b;
}
bool BFS() {
p=u=1;
memset(viz,0,n+1);
q[1]=0;
viz[0]=1;
while(p<=u) {
if(q[p]==n) {
p++;
continue;
}
nod=q[p];
for(it=L[nod].begin();it!=L[nod].end();it++) {
if(viz[*it] || C[nod][*it]==F[nod][*it])
continue;
u++;
q[u]=*it;
viz[*it]=1;
T[*it]=nod;
}
p++;
}
return viz[n];
}
int main() {
ifstream f("harta.in");
ofstream g("harta.out");
f>>n;
for(i=1;i<=n;i++) {
f>>x>>y;
C[0][i]=x;
C[n+i][2*n+1]=y;
L[0].push_back(i);
L[i].push_back(0);
L[n+i].push_back(2*n+1);
L[2*n+1].push_back(n+i);
for(j=1;j<=n;j++)
if(i!=j) {
C[i][n+j]=1;
L[i].push_back(n+j);
L[n+j].push_back(i);
}
}
n<<=1;
n++;
while( BFS() ) {
for(it=L[n].begin();it!=L[n].end();it++) {
if(!viz[*it] || C[*it][n]==F[*it][n])
continue;
T[n]=*it;
Min=INF;
for(i=n;i!=0;i=T[i])
Min=minim(Min,C[T[i]][i]-F[T[i]][i]);
if(Min==0)
continue;
for(i=n;i!=0;i=T[i]) {
F[T[i]][i]+=Min;
F[i][T[i]]-=Min;
}
}
}
for(i=1;i<=n/2;i++) {
for(it=L[i].begin();it!=L[i].end();it++)
if(*it!=0 && F[i][*it]!=0) {
k++;
sol[k][0]=i;
sol[k][1]=*it-n/2;
}
}
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<sol[i][0]<<" "<<sol[i][1]<<"\n";
return 0;
}