Pagini recente » Cod sursa (job #2476530) | Statistici Zuga Tudor (tudorzuga) | Cod sursa (job #1218596) | Cod sursa (job #2143809) | Cod sursa (job #2959746)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;
int n;
int s,t;
struct muchie{
int nodDest;
int capacitate;
int flux;
int revers;
muchie(int dest, int cap, int fl, int revers1)
: nodDest(dest), capacitate(cap), flux(fl), revers(revers1){};
};
bool bfs(int vizitate[], vector<muchie> muchii[]){
memset(vizitate, 0, sizeof(int)*(n*2+2));
queue<int> q;
for(muchie& m : muchii[s])
if(m.flux != m.capacitate){
vizitate[m.nodDest] = true;
q.push(m.nodDest);
}
while(!q.empty()){
int nod = q.front(); q.pop();
if(nod==t)
return true;
for(muchie& m : muchii[nod]){
if(!vizitate[m.nodDest] && m.flux < m.capacitate){
vizitate[m.nodDest] = true;
q.push(m.nodDest);
}
}
}
return false;
}
int trimite(int start, int flux, int vizitate[], vector<muchie> muchii[]){
if(start==t)
return flux;
vizitate[start]=1;
for(muchie& m : muchii[start]){
if(!vizitate[m.nodDest] && m.flux < m.capacitate){
int fluxC;
if(flux < m.capacitate - m.flux)
fluxC = flux;
else
fluxC = m.capacitate - m.flux;
int fluxT = trimite(m.nodDest, fluxC, vizitate, muchii);
if(fluxT > 0){
m.flux += fluxT;
if(m.revers!=-1){
muchii[m.nodDest][m.revers].flux -= fluxT;
}
return fluxT;
}
}
}
return 0;
}
int **indexMuchii;
int main(){
ifstream fin("harta.in");
ofstream fout("harta.out");
fin>>n;
s=0, t=n*2+1;
vector<muchie> muchii[n*2+2];
int **indexMuchii=new int*[n+1];
for(int i=1;i<=n;i++)
indexMuchii[i]=new int[n+1];
int x,y;
for(int i=1;i<=n;i++){
fin>>x>>y;
muchii[s].push_back(muchie(i,x,0,-1));
muchii[i+n].push_back(muchie(t, y, 0, -1));
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
int lastPozi = muchii[i].size();
int lastPozj = muchii[j].size();
indexMuchii[i][j]=lastPozi;
muchii[i].push_back(muchie(j+n,1,0,lastPozj));
muchii[j+n].push_back(muchie(i,0,0,lastPozi));
}
}
int vizitate[n*2+2];
int vizitate2[n*2+2];
while(bfs(vizitate, muchii)){
memset(vizitate2, 0, sizeof(int)*(n*2+2));
while(trimite(s, INT_MAX, vizitate2, muchii));
}
vector<pair<int,int>> rez;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j)
continue;
if(muchii[i][indexMuchii[i][j]].flux==1)
rez.push_back({i,j});
}
fout<<rez.size()<<"\n";
for(pair<int,int>& m : rez)
fout<<m.first<<" "<<m.second<<"\n";
return 0;
}