Pagini recente » Cod sursa (job #2348893) | Cod sursa (job #522877) | Cod sursa (job #3144329) | Cod sursa (job #2968967) | Cod sursa (job #2469052)
#include <fstream>
#include <bitset>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,i,j,k,nod,vec,flux[205][205],c[205][205],t[205],m,cnt;
vector <int> l[205];
bitset <205> f;
deque <int> d;
pair<int,int> sol[10001];
bool bfs(){
f.reset();
d.push_back(0);
f[0]=1;
while(!d.empty()){
nod=d.front();
for(i=0;i<l[nod].size();i++){
vec=l[nod][i];
if(!f[vec] && c[nod][vec]-flux[nod][vec]>0){
d.push_back(vec);
t[vec]=nod;
f[vec]=1;
}
}
d.pop_front();
}
return f[n];
}
int main(){
fin>>n;
for(i=1;i<=n;i++)
l[0].push_back(i), l[i].push_back(0);
for(i=n+1;i<=2*n;i++)
l[2*n+1].push_back(i), l[i].push_back(2*n+1);
for(i=1;i<=n;i++){
fin>>j>>k;
c[0][i]=j;
c[i+n][2*n+1]=k;
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(j-i!=n){
l[i].push_back(j);
l[j].push_back(i);
c[i][j]=1;
}
while(bfs()){
for(i=0;i<l[2*n+1].size();i++){
nod=l[2*n+1][i];
if(f[nod] && c[nod][2*n+1]-flux[nod][2*n+1]>0){
m=c[nod][2*n+1]-flux[nod][2*n+1];
while(nod!=0){
m=min(m,c[t[nod]][nod]-flux[t[nod]][nod]);
nod=t[nod];
}
nod=l[2*n+1][i];
flux[nod][2*n+1]+=m;
flux[2*n+1][nod]-=m;
while(nod!=0){
flux[t[nod]][nod]+=m;
flux[nod][t[nod]]-=m;
nod=t[nod];
}
}
}
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(flux[i][j]==1)
sol[++cnt]=make_pair(i,j-n);
fout<<cnt<<"\n";
for(i=1;i<=cnt;i++)
fout<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}