Pagini recente » Cod sursa (job #847856) | Cod sursa (job #1149525) | Cod sursa (job #1335110) | Cod sursa (job #83261) | Cod sursa (job #1332541)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define NMax 205
#define inf 2100000000
ifstream f("harta.in");
ofstream g("harta.out");
int n,m;
vector<int> v[NMax];
queue<int> cd;
int C[NMax][NMax];
int F[NMax][NMax];
bool viz[NMax];
int ant[NMax];
int S,D;
bool BFS(int s)
{
int i;
for(i=S;i<=D;++i) viz[i] = false;
viz[s] = true;
cd.push(s);
while(!cd.empty())
{
s = cd.front(); cd.pop();
if(s!=D) for(i=0;i<v[s].size();++i) if(!viz[v[s][i]] && F[s][v[s][i]] < C[s][v[s][i]])
{
ant[v[s][i]] = s;
viz[v[s][i]] = true;
cd.push(v[s][i]);
}
}
return viz[D];
}
int main()
{
int i,j,a,b;
f>>n;
S = 0; D = 2*n+1;
for(i=1;i<=n;++i)
{
f>>a>>b;
v[S].push_back(i);
v[i].push_back(S);
v[n+i].push_back(D);
v[D].push_back(n+i);
C[S][i] += a;
C[n+i][D] += b;
}
for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(i!=j)
{
v[i].push_back(n+j);
v[n+j].push_back(i);
C[i][n+j] = 1;
}
int newflow, s;
while(BFS(S)) for(i=0;i<v[D].size();++i)
{
ant[D] = v[D][i];
newflow = inf;
s = D;
while(s != S)
{
newflow = min( newflow , C[ant[s]][s] - F[ant[s]][s] );
s = ant[s];
}
s = D;
while(s != S)
{
F[ant[s]][s] += newflow;
F[s][ant[s]] -= newflow;
s = ant[s];
}
}
int sol = 0;
for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(F[i][n+j] == 1) sol++; g<<sol<<"\n";
for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(F[i][n+j] == 1) g<<i<<" "<<j<<"\n";
f.close();
g.close();
return 0;
}