Pagini recente » Cod sursa (job #1162510) | Cod sursa (job #701708) | Cod sursa (job #1543830) | Cod sursa (job #2805034) | Cod sursa (job #3189801)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define maxx INT_MAX
class Graf{
private:
int n;
int cap[101][101], flux[101][101];
vector<int> t;
vector<vector<int>> adc;
public:
Graf(int n) : n(n){
adc.resize(n+1);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cap[i][j]=0;
flux[i][j]=0;
}
}
}
void adauga_muchie(int i, int j){
adc[i].push_back(j);
adc[j].push_back(i);
cap[i][j]=1;
}
void adauga_muchie_s(int i, int x){
adc[0].push_back(i);
cap[0][i]=x;
}
void adauga_muchie_d(int j, int y){
adc[j].push_back(n-1);
cap[j][n-1]=y;
}
int bfs (int s, int d){
deque<int> Q;
vector<int> use(d+1, 0);
t.assign(d+1, 0);
Q.push_back(s);
use[s]=1;
while(!Q.empty()){
int nod = Q.front();
Q.pop_front();
//cout<<nod<<' ';
if(nod==d) break;
for(int i=0; i<adc[nod].size(); i++){
int vecin=adc[nod][i];
if(!use[vecin]){
if((cap[nod][vecin]-flux[nod][vecin])>0){
Q.push_back(vecin);
t[vecin]=nod;
use[vecin]=1;
}
}
}
}
if(t[d]) return 1;
return 0;
}
int edmond_karp(int s, int d){
int flow = 0;
int i, mini;
while(bfs(s,d)){
mini= maxx;
i=d;
while(i!=0){
if((cap[t[i]][i] - flux[t[i]][i] )< mini)
mini = (cap[t[i]][i] - flux[t[i]][i]);
i=t[i];
}
i=d;
while(i!=0){
flux[t[i]][i] += mini;
flux[i][t[i]] -= mini;
i=t[i];
}
flow += mini;
}
return flow;
}
void taramul_nicaieri(int s, int d){
fout<<edmond_karp(s,d)<<endl;
int m = (d-1)/2;
for(int i=1; i<=m; i++){
for(int j=m+1; j<=m+m; j++){
if(flux[i][j]==1)
fout<<i<<' '<<j-m<<endl;
}
}
}
};
int main()
{
int n;
int s,d,x,y,c;
fin>>n;
s=0;
d=n+n+1;
Graf g(d+1);
for(int i=1; i<=n; i++){
fin>>x>>y;
int j=n+i;
g.adauga_muchie_s(i,x);
g.adauga_muchie_d(j,y);
}
for(int i=1; i<=n; i++){
for(int j=n+1; j<=n+n; j++){
if((i%n)!=(j%n)) {
g.adauga_muchie(i,j);
}
}
}
g.taramul_nicaieri(s,d);
return 0;
}