Pagini recente » Cod sursa (job #385444) | Cod sursa (job #1354745) | Cod sursa (job #1359483) | Cod sursa (job #3140658) | Cod sursa (job #578831)
Cod sursa(job #578831)
#include<cstring>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
#define pb push_back
const char in[]="harta.in";
const char out[]="harta.out";
const int Max_N = 210;
vector<int>G[Max_N];
bitset<Max_N>in_Q;
queue<int>Q;
int C[Max_N][Max_N], F[Max_N][Max_N], T[Max_N], S, D, N, x, y, min_f, flow;
inline int min(int a, int b){return ( a > b ) ? b : a;}
bool BFS()
{
in_Q.reset();
while(Q.size())Q.pop();
Q.push(S);
in_Q[S] = true;
memset(T, 0, sizeof(T));
while(Q.size())
{
x = Q.front();
Q.pop();
if(x == D)return true;
for(unsigned i = 0 ; i < G[x].size() ; ++i)
{
if(C[x][G[x][i]] == F[x][G[x][i]] || in_Q[G[x][i]])continue;
T[G[x][i]] = x;
Q.push(G[x][i]);
in_Q[G[x][i]] = true;
if(G[x][i] == D) return true;
}
}
return false;
}
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d", &N);
S = 0, D = N * 2 + 1;
for(int i = 1 ; i <= N ; ++i)
{
scanf("%d %d", &x, &y);
G[S].pb(i);
G[i + N].pb(D);
G[D].pb(i + N);
C[S][i] = C[i][S] = x;
C[i + N][D] = C[D][i + N] = y;
}
for(int i = 1 ; i <= N ; ++i)
for(int j = N + 1; j < D ; ++j)
if(i != j - N)
{
G[i].pb(j);
C[i][j] = 1;
G[j].pb(i);
}
while(BFS())
{
for(unsigned i = 0 ; i < G[D].size() ; ++i){
x = G[D][i];
if(F[x][D] == C[x][D] || !in_Q[x])continue;
T[D] = x;
min_f = 0x3f3f3f3f;
for(int i = D ; i != S ; i = T[i])
min_f = min(min_f, C[T[i]][i] - F[T[i]][i]);
if(!min_f)continue;
for(int i = D ; i != S ; i = T[i])
{
F[T[i]][i] += min_f;
F[i][T[i]] -= min_f;
}
flow += min_f;
}
}
printf("%d\n", flow);
for(int i = 1 ; i <= N ; ++i)
for(int j = N ; j <= D ; ++j)
if(i != j - N && F[i][j] == 1)
printf("%d %d\n", i, j - N);
return 0;
}