Pagini recente » Cod sursa (job #3202400) | Cod sursa (job #2537103) | Cod sursa (job #297647) | Cod sursa (job #1136347) | Cod sursa (job #3190527)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;
#define dim 1002
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(int s,int d,vector<vector<int>>& cap,vector<vector<int>>& flux,vector<vector<int>>& graf,vector<int>& t) {
deque<int> deq;
vector<int> viz(d+1,0);
t.assign(d+1,0);
deq.push_back(s);
viz[s]=1;
while (!deq.empty()){
int nod=deq.front();
deq.pop_front();
if (nod==d)
break;
for (auto vec:graf[nod]) {
if (!viz[vec] && cap[nod][vec]-flux[nod][vec]>0) {
deq.push_back(vec);
t[vec]=nod;
viz[vec]=1;
}
}
}
if (t[d]!=0)
return 1;
return 0;
}
int edmondKarp(int s,int d,vector<vector<int>>& cap,vector<vector<int>>& flux,vector<vector<int>>& graf) {
int flow=0;
int mn;
vector<int> t;
while (bfs(s,d,cap,flux,graf,t)){
mn=INT_MAX;
int i=d;
while (i!=0) {
if (cap[t[i]][i]-flux[t[i]][i]<mn)
mn=cap[t[i]][i]-flux[t[i]][i];
i=t[i];
}
i=d;
while (i!=0) {
flux[t[i]][i]+=mn;
flux[i][t[i]]-=mn;
i=t[i];
}
flow+=mn;
}
return flow;
}
int main(){
int n,s,d;
s=0;
fin>>n;
d=2*n+1;
vector<vector<int>> cap(dim,vector<int>(dim,0)),flux(dim,vector<int>(dim,0)),graf(dim,vector<int>());
vector<int> t;
for (int i=1;i<=n;i++) {
int x,y;
fin>>x>>y;
int k=n+i;
graf[s].push_back(i);
graf[k].push_back(d);
cap[s][i]=x;
cap[k][d]=y;
}
for (int i=1;i<=n;i++)
for (int j=n+1;j<=2*n;j++)
if (i!=(j-n)){
graf[i].push_back(j);
graf[j].push_back(i);
cap[i][j]=1;
}
fout<<edmondKarp(s,d,cap,flux,graf)<<"\n";
for (int i=1;i<=n;i++)
for (int j=n+1;j<=2*n;j++) {
if (flux[i][j]==1)
fout<<i<<" "<<j-n<<endl;
}
return 0;
}