Pagini recente » Cod sursa (job #2643525) | Cod sursa (job #1383482) | Cod sursa (job #3127832) | Cod sursa (job #1910975) | Cod sursa (job #1161745)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define NMax 202
using namespace std;
int flux[NMax][NMax];
int cap[NMax][NMax];
vector <int> grr[NMax];
vector <pair<int,int> > sol;
queue <int> q;
int n,d,s;
int tata[NMax];
bool bfs()
{
int i;
int vf;
for(i=1;i<=d;i++)
tata[i]=0;
tata[s]=s;
q.push(s);
while(!q.empty())
{
vf=q.front();
q.pop();
if(vf!=d)
{
for(i=0;i<grr[vf].size();i++)
if((flux[vf][grr[vf][i]]!=cap[vf][grr[vf][i]])&&(!tata[grr[vf][i]]))
{
tata[grr[vf][i]]=vf;
q.push(grr[vf][i]);
}
}
}
if(tata[d])
return 1;
return 0;
}
int main()
{
int m;
int i,j;
int a,b;
int fmin,vf;
//int flow=0;
ifstream f("harta.in");
f>>n;
d=2*n+2;
s=2*n+1;
for(i=1;i<=n;i++)
{
f>>a>>b;
cap[s][i]=a;
cap[i+n][d]=b;
grr[s].push_back(i);
grr[i].push_back(s);
grr[i+n].push_back(d);
grr[d].push_back(i+n);
}
f.close();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cap[i][j+n]=1;
grr[i].push_back(j+n);
grr[j+n].push_back(i);
}
while(bfs())
{
for(i=0;i<grr[d].size();i++)
if((flux[grr[d][i]][d]!=cap[grr[d][i]][d])&&(tata[grr[d][i]]))
{
vf=grr[d][i];
tata[d]=vf;
fmin=cap[vf][d]-flux[vf][d];
while(vf!=s)
{
fmin=min(fmin,cap[tata[vf]][vf]-flux[tata[vf]][vf]);
vf=tata[vf];
}
if(fmin>0)
{
vf=d;
while(vf!=s)
{
flux[tata[vf]][vf]+=fmin;
flux[vf][tata[vf]]-=fmin;
vf=tata[vf];
}
//flow+=fmin;
}
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(flux[i][j+n])
sol.push_back(make_pair(i,j));
ofstream g("harta.out");
/*for(i=1;i<=2*n+2;i++)
{
for(j=1;j<=2*n+2;j++)
g<<cap[i][j]<<" ";
g<<'\n';
}
g<<'\n';
for(i=1;i<=2*n+2;i++)
{
for(j=1;j<=2*n+2;j++)
g<<flux[i][j]<<" ";
g<<'\n';
}
*/
g<<sol.size()<<"\n";
for(i=0;i<sol.size();i++)
g<<sol[i].first<<" "<<sol[i].second<<'\n';
//g<<flow;
g.close();
return 0;
}