Pagini recente » Cod sursa (job #1161984) | Cod sursa (job #659581) | Cod sursa (job #245723) | Cod sursa (job #2660692) | Cod sursa (job #921322)
Cod sursa(job #921322)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define Nmax 110
#define pb push_back
#define Inf 0x3f3f3f3f
int Cap[Nmax][Nmax], Flow[Nmax][Nmax], Source, Sink;
int N, DegIn, DegOut, M, Father[Nmax];
vector<int> G[Nmax];
bool Used[Nmax];
void Build_Graph()
{
scanf("%i", &N);
Source = 0;
Sink = 2 * N + 1;
for(int i = 1; i <= N; ++ i)
{
scanf("%i %i", &DegOut, &DegIn);
Cap[Source][i] = DegOut;
Cap[i + N][Sink] = DegIn;
G[Source].pb(i); G[i].pb(Source);
G[i + N].pb(Sink); G[Sink].pb(i + N);
for(int j = 1; j <= N; ++ j)
if(i != j)
{
Cap[i][j + N] = 1;
G[i].pb(j + N); G[j + N].pb(i);
}
}
}
bool BFS()
{
memset(Used, 0, sizeof(Used));
queue<int> Q;
Used[Source] = 1;
Q.push(Source);
while(!Q.empty())
{
int Node = Q.front(); Q.pop();
if(Node == Sink) continue;
for(vector<int> :: iterator it = G[Node].begin(); it != G[Node].end(); ++ it)
if(!Used[*it] && Cap[Node][*it] > Flow[Node][*it])
{
Used[*it] = 1;
Father[*it] = Node;
Q.push(*it);
}
}
return Used[Sink];
}
void MaxFlow()
{
while(BFS())
{
for(vector<int> :: iterator it = G[Sink].begin(); it != G[Sink].end(); ++ it)
if(Used[*it] && Cap[*it][Sink] != Flow[*it][Sink])
{
Father[Sink] = *it;
int MinFlow = Inf;
for(int Node = Sink; Node != Source; Node = Father[Node])
MinFlow = min(MinFlow, Cap[Father[Node]][Node] - Flow[Father[Node]][Node]);
for(int Node = Sink; Node != Source; Node = Father[Node])
{
Flow[Father[Node]][Node] += MinFlow;
Flow[Node][Father[Node]] -= MinFlow;
}
}
}
}
void GetAns()
{
int Ans = 0;
for(int i = 1; i <= N; ++ i)
for(int j = N + 1; j <= 2 * N; ++ j)
if(Flow[i][j])
Ans ++;
printf("%i\n", Ans);
for(int i = 1; i <= N; ++ i)
for(int j = N + 1; j <= 2 * N; ++ j)
if(Flow[i][j])
printf("%i %i\n", i, j - N);
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
Build_Graph();
MaxFlow();
GetAns();
return 0;
}