Cod sursa(job #2589874)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 27 martie 2020 03:35:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 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;
}