Pagini recente » Cod sursa (job #741587) | Cod sursa (job #3124408) | Cod sursa (job #3344847)
//practic un cuplaj in graf bipartit unde ne facem in primu rand partea cu nodurile out si partea cu nodurile in
// facem un nod S si tragem muchie de la el la toate nodurile din stanga (out), cu costul = nr de aparitii a nodului respectiv
// facem un nod T si tragem muchie de la toate nodurile din dreapta (in), cu costul = nr de aparitii
// tragem toate muchiile dintre cele doua parti inafara de cele de la un nod la el insasi si toate au costul 1
// facem flowul maxim si afisam muchiile cu dintre noduri cu F > 0
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 205
#define INF 1e9
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
int N, S, T, c, C[NMAX][NMAX], F[NMAX][NMAX], level[NMAX], idx[NMAX], in[NMAX], out[NMAX];
vector <int> G[NMAX];
bool bfs()
{
memset(level, -1, sizeof(level));
level[S] = 0;
queue <int> q;
q.push(S);
while(q.size())
{
int acc = q.front();
q.pop();
for(auto e : G[acc])
{
if(level[e] == -1 and C[acc][e] - F[acc][e] > 0)
{
level[e] = level[acc] + 1;
q.push(e);
}
}
}
if(level[T] == -1)
return false;
return true;
}
int dfs(int acc, int pushed)
{
if(acc == T or pushed == 0)
return pushed;
for( ; idx[acc] < G[acc].size(); idx[acc]++)
{
int e = G[acc][idx[acc]];
if(level[e] != level[acc] + 1 or C[acc][e] - F[acc][e] <= 0)
continue;
int path_flow = dfs( e, min(pushed, C[acc][e] - F[acc][e]));
if(path_flow == 0)
continue;
F[acc][e] += path_flow;
F[e][acc] -= path_flow;
return path_flow;
}
return 0;
}
int main()
{
cin >> N;
S = 0; T = 2 * N + 1;
for(int i = 1; i <= N; i++)
{
cin >> out[i] >> in[i];
if(out[i])
{
G[S].push_back(i);
G[i].push_back(S);
C[S][i] = out[i];
}
if(in[i])
{
int id = N + i;
G[id].push_back(T);
G[T].push_back(id);
C[id][T] = in[i];
}
}
for(int i = 1; i <= N; i++)
{
if(out[i])
{
for(int j = N + 1; j <= 2 * N; j++)
{
if(i != j - N and in[j - N]){
G[i].push_back(j);
G[j].push_back(i);
C[i][j] = 1;
}
}
}
}
int ok = 0, nr_drumuri = 0;
while(bfs())
{
memset(idx, 0, sizeof(idx));
while(int pushed = dfs(S, INF))
{
nr_drumuri += pushed;
}
}
cout << nr_drumuri << '\n';
for(int i = 1; i <= N; i++)
{
for(int j = N + 1; j <= 2 * N; j++)
{
if(F[i][j] > 0)
cout << i << ' ' << j - N << '\n';
}
}
return 0;
}