Pagini recente » Cod sursa (job #3167804) | Cod sursa (job #2583722) | Cod sursa (job #106863) | Cod sursa (job #192073) | Cod sursa (job #2962928)
/*
Zaharia Diana Cristiana
Explicatie problema, idee + metoda de rezolvare :
- folosim algoritmul de la flux maxim ( bfs + fluxmaxim) si il adaptam problemei curente
- construim matricea grafului pt rularea alg de flux
- dublam nodurile( n+i este dublura lui i) (avem 2*n nduri la final)
- adaugam muchii de la sursa la fiecare nod cu capacitatea egala cu gradul out 0 -> N ( sa vedem toate nodurile din
care se pleaca)
- adaugan muchii de la fiecare nod la destinatie cu cap egala cu gradul in N+1 -> 2*N + 1
(nodurile in care se vine)
- adaugam muchii de la fiecare nod la celelalte noduri (capacitatea = 1) (fara legaturi cu el insusi)
- facem flux maxim -> fluxul maxim = nr de muchii adaugate (cap 1 pe muchie ne ajuta sa numaram)
Muchiile afisate sunt cele cu capacitate = 0
*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int N, x, y, fluxmax, gr[1001][1001], t[1001], in[1001], out[1001];
bool viz[1001];
queue <int> q;
bool bfs()
{
while (q.empty() == false)
q.pop();
for (int i=0; i <= 2*N+1; i++){
t[i] = -1;
viz[i] = false;
}
q.push(0);
viz[0] = true;
while (q.empty() == false)
{
auto nd = q.front();
q.pop();
if (nd == 2*N + 1)
return true;
for (int i=1; i<= 2*N + 1; i++)
if (viz[i] == false && gr[nd][i] > 0){
q.push(i);
t[i] = nd;
viz[i] = true;
}
}
return false;
}
int fluxtaram(){
while(bfs()){
for (int i=N+1; i < 2*N+1; i++){
if (gr[i][2*N + 1] > 0 && viz[i] == true){
int frz = i;
vector <int> drm;
drm.push_back(2*N + 1);
drm.push_back(frz);
int nd = t[frz];
if (nd == 0)
drm.push_back(nd);
else{
while (nd != 0){
drm.push_back(nd);
nd = t[nd];
}
drm.push_back(0);
}
reverse(drm.begin(), drm.end());
int capmin = 1000000;
for(long long unsigned int i=0; i<drm.size()-1; i++)
capmin = min(capmin, gr[drm[i]][drm[i+1]]);
fluxmax = fluxmax + capmin;
for(long long unsigned int i=0; i<drm.size()-1; i++){
gr[drm[i]][drm[i+1]] = gr[drm[i]][drm[i+1]] - capmin;
gr[drm[i+1]][drm[i]] = gr[drm[i+1]][drm[i]] + capmin;
}
}
}
}
return fluxmax;
}
int main(){
f >> N;
// cin >> N;
for (int i=1; i <= N; i++){
f >> x >> y;
// cin >> x >> y;
out[i] = x;
in[i] = y;
gr[0][i] = out[i];
gr[N+i][2*N+1] = in[i];
for (int nd=1; nd <= N; nd++)
if (nd != i)
gr[i][N+nd] = 1;
}
fluxtaram();
g << fluxmax << endl;
// cout << fluxmax << endl;
for (int i=1; i <= N; i++)
for (int j=1; j<=N; j++)
if (gr[i][N+j] == 0 && i != j){
g << i << " " << j << endl;
//cout << i << " " << j << endl;
}
return 0;
}