Pagini recente » Cod sursa (job #2041650) | Cod sursa (job #387532) | Cod sursa (job #2393397) | Cod sursa (job #2491091) | Cod sursa (job #2245856)
#include <bits/stdc++.h>
#define MaxN 105
#define inf (int)(1e9)
std::ifstream InFile("harta.in");
std::ofstream OutFile("harta.out");
struct GraphStruct {
int N;
int Src, Dest;
int GradExt[MaxN], GradInt[MaxN];
int Capacity[2*MaxN][2*MaxN],
Flow[2*MaxN][2*MaxN];
GraphStruct() {Src = 0; Dest = 2*MaxN-1;}
struct NodeStruct {
std::list <int> ADC;
} Node[2*MaxN];
inline int In(int x) {return x;}
inline int Out(int x){return x+N;}
inline void AddEdge(int x, int y) {
Node[x].ADC.push_back(y);
Node[y].ADC.push_back(x);
}
int Previous[2*MaxN];
bool Seen[2*MaxN];
bool BFSFlow() {
for (int i=0; i<2*MaxN; i++)
Previous[i] = Seen[i] = 0;
std::queue <int> BFSQueue;
BFSQueue.push(Src);
Seen[Src] = 1;
int Front;
while(!BFSQueue.empty()) {
Front = BFSQueue.front();
BFSQueue.pop();
for (auto Vecin:Node[Front].ADC)
if (Vecin != Front && !Seen[Vecin] && Capacity[Front][Vecin] != Flow[Front][Vecin]) {
BFSQueue.push(Vecin);
Previous[Vecin] = Front;
Seen[Vecin] = 1;
}
} return Seen[Dest];
}
void ComputeFlow() {
while(BFSFlow()) {
for (auto Vecin:Node[Dest].ADC)
if (Seen[Vecin] && Capacity[Vecin][Dest] != Flow[Vecin][Dest]) {
int MinFlow = inf;
Previous[Dest] = Vecin;
int p = Dest;
while(p!=Src)
MinFlow = std::min(MinFlow, Capacity[Previous[p]][p] - Flow[Previous[p]][p]),
p = Previous[p];
p = Dest;
while(p!=Src)
Flow[Previous[p]][p] += MinFlow,
Flow[p][Previous[p]] -= MinFlow,
p = Previous[p];
}
}
}
void FindEdges() {
}
} Graph; // Cu graful asta construim o retea; la un nod i de la 1...N asociem un nod de interior/exterior;
// De la sursa->exterior, gradul exterior; exterior->interior, capacitate 1; interior->destinatie, gradul interior.
void Citire() {
InFile >> Graph.N;
for (int i=0, Ext, Int; i<Graph.N; i++)
InFile >> Ext >> Int,
Graph.Capacity[Graph.Src][Graph.In(i+1)] = Ext,
Graph.Capacity[Graph.Out(i+1)][Graph.Dest] = Int,
Graph.AddEdge(Graph.Src, Graph.In(i+1)),
Graph.AddEdge(Graph.Out(i+1), Graph.Dest);
}
void Rezolvare() {
for (int i=0, j; i<Graph.N; i++)
for (j=Graph.N; j<2*Graph.N; j++)
if (i != j-Graph.N)
Graph.Capacity[i+1][j+1] = 1;
for (int i=0, j; i<Graph.N; i++)
for (j=Graph.N; j<2*Graph.N; j++)
if(Graph.Capacity[i+1][j+1] | Graph.Capacity[j+1][i+1])
Graph.AddEdge(i+1, j+1);
Graph.ComputeFlow();
std::vector <std::pair <int, int>> Sol;
for (int i=0, j; i<Graph.N; i++)
for (j=Graph.N; j<2*Graph.N; j++)
if (i != j-Graph.N && Graph.Capacity[i+1][j+1] == Graph.Flow[i+1][j+1])
Sol.push_back(std::make_pair(i+1, j-Graph.N+1));
OutFile << Sol.size() << '\n';
for (int i=0; i<Sol.size(); i++)
OutFile << Sol[i].first << ' ' << Sol[i].second << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}