Pagini recente » Cod sursa (job #3152281) | Cod sursa (job #529342) | Cod sursa (job #1906715) | Cod sursa (job #782762) | Cod sursa (job #986501)
Cod sursa(job #986501)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define LE 666
int st[LE],k,father[LE];
bool viz[LE*6];
int cap[LE][LE];
bool bfs(int s,int d) {
st[(k=1)]=s;
for(int i=0; i<=d; ++i) viz[i]=false;
viz[s]=true;
for(int i=1; i<=k; ++i)
for(int j=0; j<=d; ++j)
if (cap[st[i]][j]>0&&viz[j]==false) {
viz[j]=true;
st[++k]=j;
father[j]=st[i];
if (j==d) return true;
}
return false;
}
void mflow(int S,int D) {
while (bfs(S,D)) {
int nod=D;
while (nod) {
// cout<<father[nod]<<" "<<nod<<"-----";
cap[father[nod]][nod]--;
cap[nod][father[nod]]++;
nod=father[nod];
}
// cout<<'\n';
int i;
//cout<<'\n';
// for(i=1;i<=4;++i) cout<<cap[0][i]<<" ";
}
}
int n,i;
int main() {
f>>n;
for(i=1; i<=n; ++i) {
int xx,yy;
f>>xx>>yy;
cap[0][i]=xx;
cap[i+n][n+n+1]=yy;
}
for(i=1; i<=n; ++i)
for(int j=1; j<=n; ++j) if (i!=j)
cap[i][j+n]=1;
mflow(0,n+n+1);
int M=0;
for(i=1;i<=n;++i)
for(int j=1;j<=n;++j) if (i!=j&&cap[i][j+n]==0) ++M;
g<<M<<" "<<'\n';
for(i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if (i!=j&&cap[i][j+n]==0) g<<i<<" "<<j<<'\n';
// cout<<flow<<'\n';
//g<<flow<<'\n'
f.close();
g.close();
return 0;
}