Pagini recente » Cod sursa (job #1060028) | Cod sursa (job #2971375) | Cod sursa (job #2764754) | Cod sursa (job #2919806) | Cod sursa (job #2316680)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
class flow
{
public:
flow(int n, int source, int dest)
{
this->source = source;
this->dest = dest;
this->n = n;
cap.resize(n + 1, vector<int>(n + 1));
flux.resize(n + 1, vector<int>(n + 1));
vecini.resize(n + 1);
viz.resize(n + 1);
father.resize(n + 1);
}
void AddEdge(int x, int y, int c)
{
if(cap[x][y] == 0 && cap[y][x] == 0)
{
vecini[x].push_back(y);
vecini[y].push_back(x);
}
cap[x][y] += c;
}
int GetMaxFlow()
{
int ret = 0;
BFS();
while(viz[dest])
{
for(auto nod:vecini[dest])
{
if(cap[nod][dest] == flux[nod][dest] || viz[nod] == false)
continue;
father[dest] = nod;
int mn = cap[father[dest]][dest] - flux[father[dest]][dest];
nod = father[dest];
while(nod != source)
{
mn = min(mn, cap[father[nod]][nod] - flux[father[nod]][nod]);
nod = father[nod];
}
nod = dest;
while(nod != source)
{
flux[father[nod]][nod] += mn;
flux[nod][father[nod]] -= mn;
nod = father[nod];
}
ret += mn;
}
BFS();
}
return ret;
}
void GetMinCut(vector<pair<int, int> > &ret)
{
ret.reserve(GetMaxFlow());
for(int i = 1; i <= n; ++i)
for(auto j:vecini[i])
if(viz[i] == true && viz[j] == false)
ret.push_back({i, j});
}
vector<vector<int> > flux;
private:
void BFS()
{
fill(viz.begin(), viz.end(), false);
queue<int> q;
q.push(source);
viz[source] = true;
while(q.empty() == false)
{
int nod = q.front();
q.pop();
if(nod == dest)
continue;
for(auto v:vecini[nod])
{
if(cap[nod][v] == flux[nod][v] || viz[v])
continue;
viz[v] = true;
q.push(v);
father[v] = nod;
}
}
}
int source, dest;
int n;
vector<bool> viz;
vector<vector<int> > vecini;
vector<vector<int> > cap;
vector<int> father;
};
int main()
{
ifstream in("harta.in");
int n;
in >> n;
int source = 2 * n + 1, dest = 2 * n + 2;
flow gr(dest, source, dest);
for(int i = 1; i <= n; ++i)
for(int j = n+1; j <= 2 * n; ++j)
if(j != n+i)
gr.AddEdge(i, j, 1);
int x, y;
for(int i = 1; i <= n; ++i)
{
in >> x >> y;
gr.AddEdge(source, i, x);
gr.AddEdge(n+i, dest, y);
}
in.close();
ofstream out("harta.out");
out << gr.GetMaxFlow() << "\n";
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(gr.flux[i][n+j] != 0)
out << i << " " << j << "\n";
out.close();
return 0;
}