Pagini recente » Cod sursa (job #1551475) | Istoria paginii runda/oji2012.1 | Istoria paginii utilizator/novakmilan | Cod sursa (job #1715879) | Cod sursa (job #792186)
Cod sursa(job #792186)
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
const int NMAX = 202;
int capacity[NMAX][NMAX],flux[NMAX][NMAX],viz[NMAX],c[NMAX*NMAX],p[NMAX];
vector <int> v[NMAX];
vector < pair < int , int > > m;
int bfs(int n)
{
int st,dr,nod;
st=1;
dr=1;
c[st]=0;
memset(viz,0,sizeof(viz));
viz[0]=1;
while(st<=dr) {
nod=c[st];
st++;
for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
if(viz[*it]==0 && capacity[nod][*it]>flux[nod][*it]) {
viz[*it]=1;
c[++dr]=*it;
p[*it]=nod;
if(*it==(2*n+1))
return 1;
}
}
return 0;
}
void scrie(int n)
{
int i,j;
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++)
cout<<flux[i][j+n]<<" ";
cout<<endl;
}
cout<<endl;
}
void graf(int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j) {
capacity[i][j+n]=1;
v[i].push_back(j+n);
v[j+n].push_back(i);
}
for(i=1;i<=n;i++) {
v[0].push_back(i);
v[i].push_back(0);
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
}
}
int main ()
{
int n,i,j,in,out,fluxcurent,nod;
ifstream f("harta.in");
ofstream g("harta.out");
f>>n;
graf(n);
for(i=1;i<=n;i++) {
f>>out>>in;
capacity[0][i]=out;
capacity[i+n][2*n+1]=in;
}
f.close();
while(bfs(n)) {
for(nod=2*n+1;nod!=0;nod=p[nod]) {
flux[p[nod]][nod]++;
flux[nod][p[nod]]--;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(flux[i][j+n]==1)
m.push_back(make_pair(i,j));
g<<m.size()<<'\n';
for(vector < pair < int , int > > :: iterator it=m.begin();it!=m.end();it++)
g<<it->first<<" "<<it->second<<'\n';
g.close();
return 0;
}