Pagini recente » Cod sursa (job #463525) | Cod sursa (job #1012584) | Cod sursa (job #2955048) | Cod sursa (job #1996384) | Cod sursa (job #2962264)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>>gr;
int flow[201][201];
int father[1002], visited[1002];
bool bfs(int n, int src, int dest)
{
for(int i=1; i<dest; i++)
{
father[i] = 0;
visited[i] = 0;
}
visited[dest]=0;
queue<int> vertexes;
vertexes.push(src);
while(!vertexes.empty())
{
int currentNode = vertexes.front();
vertexes.pop();
for(auto extr2: gr[currentNode])
{
if(!visited[extr2] and flow[currentNode][extr2]>0) //daca nu am vizitat nodul extr2
//si capacitatea muchiei formata din nodul curent si extremitatea 2 permite trecerea flow-ului
{
father[extr2] = currentNode;
if(extr2 == dest)
return true;
vertexes.push(extr2);
visited[extr2] = 1;
}
}
}
return false; //nu am gasit un drum de la sursa la destinatie, inseamna nu mai am drumuri si ca am ajuns la flux maxim
}
int fordFulkerson(int n, int src, int dest)
{
int u, v, max_flow_for_route, currentNode;
int srcAux = src, destAux = dest, fNode, finalFlow = 0;
while(bfs(n, src, dest))
{
max_flow_for_route = INT_MAX - 1 ;
srcAux = src;
destAux = dest;
while(destAux!=srcAux)
{
//calculez flow-ul maxim de transmis pe drumul gasit de bfs
max_flow_for_route = min(max_flow_for_route, flow[father[destAux]][destAux]);
destAux = father[destAux];
}
destAux = dest;
srcAux = src;
//acum updatez graful rezidual pe drumul gasit de bfs
while(destAux!=srcAux)
{
fNode = father[destAux];
flow[fNode][destAux] -= max_flow_for_route; //muchia mea pe directia corecta va avea o capacitate mai mica de flow
flow[destAux][fNode] += max_flow_for_route; //muchia pe directia inversa va avea mai mult flow de dat
//logic pt ca voi avea mai mult flow de extras
destAux = fNode;
}
finalFlow += max_flow_for_route; //adun flow-ul drumului la flow-ul final
}
return finalFlow;
}
int main()
{
int n,m,inNode,outNode,count=0;
f>>n;
int src = 0;
int dst = 2*n +1;
int delay = n;
gr.resize(201);
for(int i=1; i<=n; i++)
{
f>>outNode>>inNode;
gr[src].push_back(i);
gr[i+delay].push_back(dst);
flow[src][i] = outNode;
flow[i+delay][dst] = inNode;
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
{
flow[i][j] = 1;
gr[i].push_back(j);
gr[j].push_back(i);
}
fordFulkerson(n,src,dst);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(flow[i][j] == 0)
count++;
g<<count<<'\n';
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(flow[i][j] == 0)
g<<i<<' '<<j-delay<<endl;
return 0;
}