Pagini recente » Cod sursa (job #679542) | Cod sursa (job #2611639) | Cod sursa (job #901477) | Cod sursa (job #2543975) | Cod sursa (job #2421055)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
vector<int> g[210];
vector<int> sol[110];
int n;
int c[210][210];
int in[110];
int out[110];
int dad[110];
int bfs(int s,int d)
{
queue<int> q;
bool viz[1010];
memset(viz,0,sizeof viz);
q.push(s);
dad[s]=s;
int crt;
viz[0]=1;
while(!q.empty())
{
crt=q.front(); q.pop();
// cout<<crt<<'\n';
if(crt!=d)
for(int u:g[crt])
{
// cout<<u<<' '<<c[crt][u]<<'\n';
if(!viz[u] && c[crt][u])
{
viz[u]=1;
dad[u]=crt;
q.push(u);
}
}
}
return viz[d];
}
int main()
{
ifstream t1("harta.in");
ofstream t2("harta.out");
t1>>n;
int i,j;
for(i=1;i<=n;i++) t1>>out[i]>>in[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
c[i][100+j]=1;
g[i].push_back(100+j);
g[100+j].push_back(i);
}
for(i=1;i<=n;i++)
{
g[0].push_back(i);
g[i].push_back(0);
c[0][i]=out[i];
c[100+i][100+n+1]=in[i];
g[100+i].push_back(100+n+1);
g[100+n+1].push_back(100+i);
}
/*for(int u:g[0])
cout<<u<<' '; cout<<'\n';
for(i=1;i<=n;i++)
{
for(int u:g[i])
cout<<u<<' '; cout<<'\n';
}
for(i=1;i<=n;i++)
{
for(int u:g[100+i])
cout<<u<<' '; cout<<'\n';
}
for(i=1;i<=n;i++) cout<<c[0][i]<<' '; cout<<'\n';*/
int crt,maxim,flow=0,n1,n2;
int nr=0;
while(bfs(0,100+n+1))
{
// for(i=1;i<=n;i++) cout<<dad[i]<<' ';
// for(i=1;i<=n;i++) cout<<dad[100+i]<<' '; cout<<'\n';
for(int i=1;i<=n;i++)
if(dad[100+i] && c[100+i][100+n+1])
{
// cout<<i<<'\n';
dad[100+n+1]=100+i;
crt=100+n+1;
maxim=0x7fffffff;
while(crt!=dad[crt])
{
// cout<<crt<<' '<<c[dad[crt]][crt]<<'\n';
if(maxim>c[dad[crt]][crt])
maxim=c[dad[crt]][crt];
crt=dad[crt];
}
//cout<<maxim<<'\n';
flow+=maxim;
crt=100+n+1;
while(crt!=dad[crt])
{
c[crt][dad[crt]]+=maxim;
c[dad[crt]][crt]-=maxim;
crt=dad[crt];
}
}
// cout<<flow<<'\n';
}
t2<<flow<<'\n';
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if(c[j+100][i]) t2<<i<<' '<<j<<'\n';
t1.close();
t2.close();
return 0;
}