Pagini recente » Cod sursa (job #847781) | Cod sursa (job #2745726) | Cod sursa (job #3168003) | Cod sursa (job #19243) | Cod sursa (job #1980205)
#include<bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 205;
int N,c[NMAX][NMAX],f[NMAX][NMAX],pr[NMAX],viz[NMAX],M;
vector<int> v[NMAX],sol[NMAX];
void citire()
{
in>>N;
int x,y;
for(int i = 1 ; i <= N ; ++i){
in>>x>>y;
c[0][i] += x;
c[N+i][2*N+1] += y;
v[0].push_back(i);
v[i].push_back(0);
v[N+i].push_back(2*N+1);
v[2*N+1].push_back(N+i);
}
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= N ; ++j)
if(i != j){
c[i][N+j] += 1;
v[i].push_back(N+j);
v[N+j].push_back(i);
}
in.close();
}
void reset()
{
for(int i = 0 ; i <= 2*N + 1 ; ++i)
viz[i] = 0;
}
int bfs()
{
reset();
viz[0] = 1;
queue<int> Q;
Q.push(0);
while(!Q.empty())
{
int virf = Q.front();
Q.pop();
for(int i = 0 ; i < v[virf].size() ; ++i){
int now = v[virf][i];
if(viz[now] || c[virf][now] == f[virf][now])
continue;
viz[now] = 1;
pr[now] = virf;
Q.push(now);
}
}
return viz[2*N + 1];
}
void max_flow()
{
while(bfs()){
for(int i = 0 ; i < v[2*N + 1].size() ; ++i){
if(!viz[v[2*N+1][i]] || c[v[2*N+1][i]][2*N+1] == f[v[2*N+1][i]][2*N+1])
continue;
pr[2*N+1] = v[2*N+1][i];
int minim = 1 << 30;
for(int act = 2*N + 1 ; act != 0 ; act = pr[act])
minim = min(minim,c[pr[act]][act] - f[pr[act]][act]);
for(int act = 2*N + 1 ; act != 0 ; act = pr[act]){
f[pr[act]][act] += minim;
f[act][pr[act]] -= minim;
}
}
}
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= N ; ++j)
if(i != j && f[i][N+j])
sol[i].push_back(j),++M;
}
void write()
{
out<<M<<"\n";
for(int i = 1 ; i <= N ; ++i)
for(int j = 0 ; j < sol[i].size() ; ++j)
out<<i<<" "<<sol[i][j]<<"\n";
out.close();
}
int main()
{
citire();
max_flow();
write();
return 0;
}