Cod sursa(job #2047545)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 24 octombrie 2017 22:57:41
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.23 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
FILE *fin = fopen("revolutie.in", "r");
FILE *fout = fopen("revolutie.out", "w");
int n;
int vizitat[400];
vector <int> muchie[400];
int c[400][400];
int tata[400];
int f[400][400];
int minim(int a, int b)
{
    if(a<b) return a;
    return b;
}
struct selectat
{
    int x,y;
};
selectat v[400];
selectat raspunsuri[400];
int sortare(selectat a, selectat b)
{
    if(a.x < b.x) return true;
    return false;
}
int bfs()
{
    for(int i=0;i<=2*n+1;i++)
    {
        vizitat[i]=0;
    }
    queue <int> frontiera;
    frontiera.push(0);
    vizitat[0]=1;
    while(!frontiera.empty())
    {
        int nod = frontiera.front();
        frontiera.pop();
        if(nod == 2*n+1 ) continue;
        for(auto m : muchie[nod])
        {
            if(c[nod][m] == f[nod][m] || vizitat[m]==1) continue;
            tata[m] = nod;
            vizitat[m]=1;
            frontiera.push(m);
        }
    }
    return vizitat[2*n+1];
}
int main()
{
    fscanf(fin, "%d", &n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        int x;
        fscanf(fin, "%d", &x);
        if(x == 1) c[i][n+j]=1;
        muchie[i].push_back(n+j);
        muchie[n+j].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        c[0][i] = 1;
        c[n+i][2*n+1] = 1;
        muchie[0].push_back(i);
        muchie[i].push_back(0);
        muchie[2*n+1].push_back(n+i);
        muchie[n+i].push_back(2*n+1);
    }
    int fluxminim;
    int flux=0;
    while (bfs())
    {
        for(auto m : muchie[2*n+1])
        {
            if(c[m][2*n+1] == f[m][2*n+1] || vizitat[m]==0) continue;
            tata[2*n+1] = m;
            fluxminim = INF;
            int nod = 2*n+1;
            while(nod!=0)
            {
                fluxminim = minim (fluxminim, c[tata[nod]][nod] - f[tata[nod]][nod]);
                nod = tata[nod];
            }
            if(fluxminim == 0) continue;
            nod = 2*n+1;
            while(nod!=0)
            {
                f[tata[nod]][nod] += fluxminim;
                f[nod][tata[nod]] -= fluxminim;
                nod = tata[nod];
            }
            flux += fluxminim;
        }
    }
    int cnt=0;
            int rez=0;
    if(flux < n) fprintf(fout,"-1");
    else
    {
        for(int i=1;i<=n;i++)
            for(int j=n+1;j<=2*n;j++)
        {
            if(f[i][j] == 1)
            {
                cnt++;
                v[cnt].x=i;
                v[cnt].y=j-n;
            }
        }
        sort(v+1,v+cnt+1,sortare);
        for(int i=1;i<=cnt;i++)
        {
            if(v[i].y!=i)
            {
                rez++;
                raspunsuri[rez].x = i;
                raspunsuri[rez].y = v[i].y;
            }
            for(int j=1;j<=n;j++)
            {
                if(v[j].y==i)
                {
                    v[j].y=v[i].y;
                }
            }
        }
            fprintf(fout, "%d\n", rez);
    for(int i=1;i<=rez;i++)
    {
        fprintf(fout, "C %d %d\n", raspunsuri[i].x, raspunsuri[i].y);
    }
    }
    return 0;
}