Pagini recente » Cod sursa (job #2250156) | Cod sursa (job #2396087) | Cod sursa (job #1830440) | Cod sursa (job #460971) | Cod sursa (job #2075846)
#include <fstream>
#include <queue>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");
int N;
int C[205][205];
int rGraph[205][205];
int parent[205];
bool visited[205];
bool bfs(int rGraph[][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 && rGraph[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(rGraph, s, t, parent))
{
int path_flow =1000000;
for (v = t; v != s; v = parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
for (v = t; v != s; v = parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
fi>>N;
for (int i=1;i<=N;i++)
{
int dext,dint;
fi>>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++)
rGraph[i][j]=C[i][j];
/// algoritmul Ford-Fulkerson
fo<<fordFulkerson(C,0,2*N+1)<<"\n";
for (int i=1;i<=N;i++)
for (int j=N+1;j<=2*N;j++)
if (rGraph[i][j]==0 && C[i][j]==1)
fo<<i<<" "<<j-N<<"\n";
fi.close();
fo.close();
return 0;
}