Cod sursa(job #2960312)

Utilizator bogdaniliBogdan Iliescu bogdanili Data 4 ianuarie 2023 00:32:59
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#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;
}