Cod sursa(job #3183247)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 11 decembrie 2023 12:44:01
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
// Ilie Dumitru
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
const int NMAX=205, oo=(1LL<<31)-1;

struct edge
{
	int node, left, idxOther;
};

int N, M;
std::vector<edge> G[NMAX];
int ans;
int level[NMAX];
std::bitset<NMAX> saturated;

void addEdge(int u, int v, int w)
{
	G[u].push_back({v, w, (int)G[v].size()});
	G[v].push_back({u, 0, (int)G[u].size()-1});
}

void useEdge(edge& e, int flow)
{
	e.left-=flow;
	G[e.node][e.idxOther].left+=flow;
}

bool bfs(int source, int target)
{
	int i, node;
	std::queue<int> q;
	bool ok=0;

	q.push(source);
	for(i=0;i<N*2+2;++i)
		level[i]=NMAX;
	level[source]=0;

	do
	{
		node=q.front();
		q.pop();

		for(i=0;i<(int)G[node].size();++i)
		{
			if(level[node]+1<level[G[node][i].node] && G[node][i].left)
			{
				if(G[node][i].node!=target)
				{
					level[G[node][i].node]=1+level[node];
					q.push(G[node][i].node);
				}
				else
					ok=1;
			}
		}
	}while(!q.empty());

	return ok;
}

int dfs(int node, int target, int flow=oo)
{
	int i, x, nn, totalUsed=0;

	for(i=0;i<(int)G[node].size() && flow;++i)
	{
		nn=G[node][i].node;
		if(G[node][i].left)
		{
			if(nn==target)
			{
				x=std::min(flow, G[node][i].left);
				ans+=x;
				flow-=x;
				totalUsed+=x;
				useEdge(G[node][i], x);
			}
			else if(level[nn]>level[node])
			{
				x=std::min(flow, G[node][i].left);
				x=dfs(nn, target, x);
				totalUsed+=x;
				flow-=x;
				useEdge(G[node][i], x);
			}
		}
	}

	return totalUsed;
}

bool dinic(int source, int target)
{
	if(bfs(source, target))
	{
		saturated.reset();
		dfs(source, target);

		return 1;
	}

	return 0;
}

int main()
{
	FILE* f=fopen("harta.in", "r"), *g=fopen("harta.out", "w");
//	FILE* f=stdin, *g=stdout;
	int i, a, b, j;

	fscanf(f, "%d", &N);
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			if(i!=j)
				addEdge(i, j+N, 1);
	for(i=1;i<=N;++i)
	{
		fscanf(f, "%d%d", &a, &b);
		addEdge(0, i, a);
		addEdge(i+N, 2*N+1, b);
	}

	while(dinic(0, 2*N+1));

    fprintf(g, "%d\n", ans);
    for(i=1;i<=N;++i)
		for(j=0;j<(int)G[i].size();++j)
			if(!G[i][j].left && G[i][j].node)
				fprintf(g, "%d %d\n", i, G[i][j].node-N);

	fclose(f);
	fclose(g);
	return 0;
}