Pagini recente » Cod sursa (job #1661811) | Cod sursa (job #956186) | Cod sursa (job #2718532) | Cod sursa (job #230508) | Cod sursa (job #886528)
Cod sursa(job #886528)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define pb push_back
#define maxn 250
#define forEach(G) for( typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it)
ifstream in("harta.in");
ofstream out("harta.out");
vector<int> graf[maxn];
int Q[maxn];
int TT[maxn];
int F[maxn][maxn];
int C[maxn][maxn];
bool viz[maxn];
int n;
int start,end;
bool BFS()
{
int i,nod;
memset(TT,0,sizeof(TT));
memset(viz,0,sizeof(viz));
Q[0]=1;
Q[1]=start;
TT[start]=-1;
viz[start]=1;
for(i=1;i<=Q[0];++i)
{
nod = Q[i];
if(nod == end)
continue;
forEach(graf[nod])
{
if(viz[*it] || C[nod][*it] == F[nod][*it])
continue;
TT[*it] = nod;
viz[*it]=1;
Q[++Q[0]]=*it;
}
}
return TT[end];
}
void chk()
{
int nod;
bool good;
good = 1;
for(nod = end; nod != start; nod = TT[nod])
if(F[TT[nod]][nod]== C[TT[nod]][nod])
{
good = 0;
return;
}
if(!good)
return ;
for(nod = end;nod != start; nod = TT[nod])
{
F[TT[nod]][nod]++;
F[nod][TT[nod]]--;
}
}
void aug()
{
forEach(graf[end])
{
if(!TT[*it] || F[*it][end] == C[*it][end])
continue;
TT[end] = *it;
chk();
}
}
int main()
{
int i,inc,outg,j;
in >> n;
start = 0;
int show=0;
end = 2*n+1;
for(i=1;i<=n;++i)
{
in >> outg >> inc;
show += outg;
graf[start].pb(i);
graf[i].pb(start);
graf[i+n].pb(end);
graf[end].pb(i+n);
C[start][i] = outg;
C[i+n][end] = inc;
}
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
if(i != j-n)
{
graf[i].pb(j);
graf[j].pb(i);
C[i][j] = 1;
}
out << show << "\n";
for(;BFS();aug());
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
if(F[i][j]==1)
out << i << " " << j-n << "\n";
}