Pagini recente » Cod sursa (job #562704) | Cod sursa (job #2506128) | Cod sursa (job #45988) | Cod sursa (job #607452) | Cod sursa (job #761826)
Cod sursa(job #761826)
#include<fstream>
#include<queue>
#include<vector>
#define pb push_back
#define foreach(V) for(vector<int>::iterator it = G[V].begin(); it != G[V].end(); it++)
#define nmax 206
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[nmax][nmax], F[nmax][nmax], TT[nmax];
int N, S, x, y, D, sum;
bool use[nmax];
vector<int> G[nmax];
bool BFS()
{
for(int i = 1; i <= D; i++, use[i] = false, TT[i] = -1);
queue<int> q;
use[S] = true;
q.push(S);
TT[S] = -1;
while(!q.empty())
{
int x = q.front();
q.pop();
foreach(x)
{
int nod =*it;
if(C[x][nod] - F[x][nod] > 0 && use[nod] ==false)
{
use[nod] = true;
q.push(nod);
TT[nod] = x;
}
}
}
return use[D];
}
void solve()
{
while( BFS())
foreach(D)
{
int vmin = 1<<30, nod = *it;
if(use[nod] && C[nod][D] - F[nod][D] > 0 )
{
for(int i = nod; i != S; i = TT[i] )
vmin = min(vmin, C[TT[i]][i] - F[TT[i]][i]);
for(int i = nod; i != S; i = TT[i] )
F[TT[i]][i] += vmin,
F[i][TT[i]] -= vmin;
}
}
}
void read()
{
fin >> N;
D = 2 * N + 1;
S = 0;
for(int i = 1; i <= N; i++)
{
fin >>x >>y;
G[0].pb(i);
G[i].pb(0);
G[i + N].pb(D);
G[D].pb(i+N);
C[S][i] = x;
C[i + N][D] = y;
sum += x;
}
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N ;j++)
if(i!=j){
G[i].pb(j + N),
G[j + N].pb(i),
C[i][j+ N] = 1;
}
}
int main()
{
read();
solve();
fout << sum <<'\n';
for(int i = 1; i <= N ;i++)
for(int j = 1; j <= N ;j++)
if(i != j && F[i][j + N])
fout<< i << " " << j <<'\n' ;
fin.close();
return 0;
}