Cod sursa(job #1828304)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 13 decembrie 2016 01:06:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define MaxN 355
#define INF 2140000000
#define MAX 131072
using namespace std;

FILE *IN,*OUT;


int pos=0,N,A,B,flow[MaxN][MaxN],cap[MaxN][MaxN],father[MaxN];
bool found[MaxN];
char f[MAX];
vector <int>Graph[MaxN];
queue<int>Q;

inline void Read(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
}

bool BFS(int start,int end)
{
	memset(father,0,sizeof father);
	memset(found,0,sizeof found);
	Q.push(start);
	while(!Q.empty())
	{
		for(int i=0;i<Graph[Q.front()].size();i++)
			if(!found[Graph[Q.front()][i]]&&cap[Q.front()][Graph[Q.front()][i]]>flow[Q.front()][Graph[Q.front()][i]])
				Q.push(Graph[Q.front()][i]),father[Graph[Q.front()][i]]=Q.front(),found[Graph[Q.front()][i]]=true;
		Q.pop();
	}
	if(father[end])
		return true;
	else return false;
}
int Flow(int start,int end)
{
	int F=0,Min;
	while(BFS(start,end))
	{
		for(int i=N+1;i<=2*N;i++)
			if(found[i]&&cap[i][end]>flow[i][end])
			{
				Min=cap[i][end]-flow[i][end];
				for(int j=i;j!=start;j=father[j])
					Min=min(Min,cap[father[j]][j]-flow[father[j]][j]);
				flow[i][end]+=Min,flow[end][i]-=Min;
				for(int j=i;j!=start;j=father[j])
					flow[father[j]][j]+=Min,flow[j][father[j]]-=Min;
				F+=Min;
			}
	}
	return F;
}
int main()
{
	IN=fopen("harta.in","r");
	OUT=fopen("harta.out","w");
	fread(f,1,MAX,IN);

	Read(N);
	for(int i=1;i<=N;i++)
	{
		Read(A),Read(B);
		Graph[0].push_back(i);
		Graph[i].push_back(0);
		cap[0][i]=A;
		Graph[2*N+1].push_back(N+i);
		Graph[N+i].push_back(2*N+1);
		cap[i+N][2*N+1]=B;
		for(int j=1;j<=N;j++)
		{
			if(i==j)continue;
			Graph[i].push_back(N+j);
			Graph[N+j].push_back(i);
			cap[i][N+j]=1;
		}
	}
	fprintf(OUT,"%d \n",Flow(0,2*N+1));
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{
			if(j==i)continue;
			if(flow[i][j+N]==1)
				fprintf(OUT,"%d %d \n",i,j);
		}
	return 0;
}