Cod sursa(job #2075845)

Utilizator DragosBledeaDragos Bledea DragosBledea Data 25 noiembrie 2017 18:53:18
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#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[])
{
    memset(visited, 0, sizeof(visited));
    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;
}