Pagini recente » Cod sursa (job #2845733) | Cod sursa (job #3196438) | Cod sursa (job #3171025) | Cod sursa (job #2897708) | Cod sursa (job #2960312)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int N;
int C[205][205];
int residualGraph[205][205];
int parent[205];
bool visited[205];
bool bfs(int residualGraph[][205], int s, int t, int parent[])
{
for (int i=0;i<=2*N+1;i++)
visited[i]=0;
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v = 0; v <= 2*N+1; v++)
{
if (visited[v] == false && residualGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return (visited[t] == true);
}
int fordFulkerson(int graph[][205], int s, int t)
{
int u, v;
int max_flow = 0;
while (bfs(residualGraph, s, t, parent))
{
int path_flow =1000000;
for (v = t; v != s; v = parent[v])
{
u = parent[v];
path_flow = min(path_flow, residualGraph[u][v]);
}
for (v = t; v != s; v = parent[v])
{
u = parent[v];
residualGraph[u][v] -= path_flow;
residualGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
fin>>N;
for (int i=1;i<=N;i++)
{
int dext,dint;
fin>>dext>>dint;
C[0][i]=dext;
C[i+N][2*N+1]=dint;
}
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
if (i!=j)
C[i][j+N]=1;
for (int i=0;i<=2*N+1;i++)
for (int j=0;j<=2*N+1;j++)
residualGraph[i][j]=C[i][j];
fout<<fordFulkerson(C,0,2*N+1)<<"\n";
for (int i=1;i<=N;i++)
for (int j=N+1;j<=2*N;j++)
if (residualGraph[i][j]==0 && C[i][j]==1)
fout<<i<<" "<<j-N<<"\n";
return 0;
}