Pagini recente » Cod sursa (job #874490) | Clasament preONI 2007, Clasele 11-12 | Cod sursa (job #1195372) | Cod sursa (job #3225445) | Cod sursa (job #1093347)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N=110;
ifstream cin("harta.in");
ofstream cout("harta.out");
int gi[MAX_N];
int go[MAX_N];
int cap[2*MAX_N][2*MAX_N];
int flux[2*MAX_N][2*MAX_N];
vector<int> A[2*MAX_N];
int n;
bool viz[2*MAX_N];
int dad[2*MAX_N];
void graf(int N) {
n=2*N+1;
for(int i=1;i<=N;i++) {
cap[0][i]=go[i];
if(go[i]) {
A[0].push_back(i);
A[i].push_back(0);
}
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
if(i==j) {
continue;
}
cap[i][j+N]=1;
A[i].push_back(j+N);
A[j+N].push_back(i);
}
}
for(int i=1;i<=N;i++) {
cap[i+N][n]=gi[i];
if(gi[i]) {
A[i+N].push_back(n);
A[n].push_back(i+N);
}
}
}
bool bfs() {
memset(viz,0,sizeof(viz));
memset(dad,0,sizeof(dad));
queue<int> Q;
Q.push(0);
viz[0]=true;
while(!Q.empty()) {
int nod=Q.front();
Q.pop();
for(auto it=A[nod].begin(); it!=A[nod].end(); it++) {
if(!viz[*it]&&flux[nod][*it]<cap[nod][*it]) {
Q.push(*it);
//printf("%d\n",*it);
viz[*it]=true;
dad[*it]=nod;
}
}
}
return viz[n];
}
int maxflow() {
int fluxmax=0;
while(bfs()) {
for(auto it=A[n].begin(); it!=A[n].end(); it++) {
if(!viz[*it]||cap[*it][n]==flux[*it][n]) {
continue;
}
int nod=n;
dad[n]=*it;
int ans=cap[dad[nod]][nod]-flux[dad[nod]][nod];
while(nod) {
ans=min(cap[dad[nod]][nod]-flux[dad[nod]][nod],ans);
nod=dad[nod];
}
if(!ans) {
continue;
}
fluxmax+=ans;
nod=n;
while(nod) {
flux[dad[nod]][nod]+=ans;
flux[nod][dad[nod]]-=ans;
nod=dad[nod];
}
}
}
return fluxmax;
}
void afisare(int n) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(flux[i][j+n]==1) {
cout<<i<<' '<<j<<'\n';
}
}
}
}
int main() {
int N;
cin>>N;
for(int i=1;i<=N;i++) {
cin>>go[i]>>gi[i];
}
graf(N);
cout<<maxflow()<<'\n';
afisare(N);
return 0;
}