Pagini recente » Cod sursa (job #1359170) | Cod sursa (job #2201838) | Cod sursa (job #1145184) | Cod sursa (job #1318244) | Cod sursa (job #444867)
Cod sursa(job #444867)
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 401;
const int maxm = maxn * maxn;
const int SURSA = 300;
const int DEST = 299;
queue <int> Q;
vector <int> G[maxn];
int i , j , n , a , b , res;
int C[maxn][maxn] , F[maxn][maxn] , dad[maxn];
bool seen[maxn];
bool BF ()
{
int i;
memset ( seen , 0 , sizeof(seen));
seen[SURSA] = 1;
while ( ! Q.empty() ) Q.pop();
Q.push(SURSA);
for( ; !Q.empty() ; ) {
int node = Q.front() ; Q.pop();
if ( node == DEST ) break;
for(i = 0 ; i < G[node].size() ; ++i )
{
int act = G[node][i];
if ( F[node][act] < C[node][act] && seen[act] == 0 ) {
Q.push(act);
dad[act] = node;
seen[act] = 1;
}
}
}
return seen[DEST];
}
void flow ()
{
int i;
for( ; BF() ; ) {
for ( i = 0 ; i < G[DEST].size() ;++i ) {
int act = G[DEST][i];
if ( seen[act] == 0 || F[act][DEST] == C[act][DEST] ) continue ;
int minflow = 1000001;
dad[DEST] = act;
for( act = DEST; act != SURSA ; act = dad[act] )
minflow = min ( minflow ,C[dad[act]][act] - F[dad[act]][act]);
for( act = DEST ; act != SURSA ; act = dad[act] )
F[dad[act]][act] += minflow ,
F[act][dad[act]] -= minflow;
}
}
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
for( scanf("%d",&n) , i = 1 ; i <= n ; ++i ) {
scanf("%d %d",&a,&b);
C[SURSA][i] = a;
C[i + 100][DEST] = b;
res += a;
}
for( i = 1 ; i <= n ; ++i ) {
G[SURSA].push_back(i);
G[i].push_back(SURSA);
G[i + 100].push_back(DEST);
G[DEST].push_back(i + 100);
}
for( i = 1 ; i <= n ; ++i )
for( j = 1 ; j <= n ; ++j ) {
if ( i != j ) C[i][j + 100] = 1;
G[i].push_back(j + 100);
G[j + 100].push_back(i);
}
flow ();
printf("%d\n",res);
for( i = 1 ; i <= n ; ++i )
for( j = 1 ; j <= n ; ++j )
if ( F[i][j + 100] == 1 ) printf("%d %d\n",i,j);
return 0;
}