Pagini recente » Cod sursa (job #3157926) | Cod sursa (job #1783316) | Cod sursa (job #58009) | Cod sursa (job #1768606) | Cod sursa (job #3185057)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define maxx INT_MAX
#define N 1001
int cap[N][N], flux[N][N];
vector<int> t;
vector<int> adc[N];
int n;
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;
//cout<<"hdx";
while(bfs(s,d)){
//cout<<"hdx";
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){
//cout<<i<<' ';
flux[t[i]][i] += mini;
flux[i][t[i]] -= mini;
i=t[i];
}
//cout<<endl;
flow += mini;
}
return flow;
}
int main()
{
int s,d,x,y,c;
fin>>n;
s=0;
d=n+n+1;
for(int i=1; i<=n; i++){
fin>>x>>y;
int j=n+i;
//adc[i].push_back(s);
adc[s].push_back(i);
//adc[d].push_back(j);
adc[j].push_back(d);
cap[s][i]=x;
cap[j][d]=y;
}
for(int i=1; i<=n; i++){
for(int j=n+1; j<=n+n; j++){
if((i%n)!=(j%n)) {
adc[i].push_back(j);
adc[j].push_back(i);
cap[i][j]=1;
}
}
}
/*for(int i=0; i<=n+n+1; i++){
cout<<i<<": ";
for(int j=0; j<adc[i].size(); j++){
cout<<adc[i][j]<<", "<<cap[i][adc[i][j]]<<" ";
}
cout<<endl;
}*/
fout<<edmond_karp(s,d)<<endl;
for(int i=1; i<=n; i++){
for(int j=n+1; j<=n+n; j++){
if(flux[i][j]==1)
fout<<i<<' '<<j-n<<endl;
}
}
return 0;
}