Cod sursa(job #478012)

Utilizator APOCALYPTODragos APOCALYPTO Data 17 august 2010 01:15:58
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
int source=1, sink;
vector<int> G[2010];
int ns,ni,m,r,c,C[2010][2010],F[2010][2010],viz[4010],ante[4010];
long long flow=0;
int BFS()
{queue<int> q;
vector<int>::iterator it;
 memset(viz,0,sizeof(viz));
 memset(ante,0,sizeof(ante));
 q.push(source);
 viz[source]=1;

 while(!q.empty())
 {
     u=q.front();
     q.pop();
     for(it=G[u].begin();it!=G[u].end();it++)
     {
         if(viz[*it]==0)
          if(F[u][*it]<C[u][*it])
          {
              viz[*it]=1;
              q.push(*it);
              ante[*it]=u;
          }

     }
     if(viz[sink]==1)
      return 1;

    return 0;
 }


}

void solve()
{vector<int>::iterator it;
   for(flow=0;BFS();)
   {
     for(it=G[sink].begin();it!=G[sink].end();it++)
       if(viz[*it]==1&&C[*it][N]>0)
       {fmin=C[*it][N]-F[*it][N];



       }


   }


}
void cit()
{int i,x,j,k,y,M;
    ifstream fin("politia.in");
    fin>>ns>>ni>>m>>r>>c;
    M=m;
    sink=2+2*(m+ns+r+ni+c);
    for(i=1;i<=m;i++)
     {
     G[1].pb(1+i);
     G[1+i].pb(1);
     C[1][1+i]=1;
     G[1+i].pb(1+M+i);
     G[1+M+i].pb(1+i);
     C[1+i][1+M+i]=1;

     }

    for(i=1;i<=ns;i++)
    {
        fin>>y;
        for(j=1;j<=y;j++)
        {
        fin>>x;
        G[M+1+x].pb(2*M+1+i);
        G[2*M+1+i].pb(M+1+x);
        C[M+1+x][2*M+1+i]=1;

        }
        G[2*M+1+i].pb(2*M+1+ns+i);
        G[2*m+1+ns+i].pb(2*M+1+i);
        C[2*m+1+i][2*m+1+ns+i]=1;
        fin>>y;
        for(j=1;j<=y;j++)
        {
            fin>>y;
            G[2*m+1+ns+i].pb(2*m+2*ns+1+x);
            G[2*m+2*ns+1+x].pb(2*m+1+ns+i);
            C[2*m+1+ns+i][2*m+2*ns+1+x]=1;

        }

    }
    for(i=1;i<=r;i++)
    {
    G[2*m+2*ns+1+i].pb(2*m+2*ns+1+i+r);
    G[2*m+2*ns+1+i+r].pb(2*m+2*ns+1+i);
    C[2*m+2*ns+1+i][2*m+2*ns+1+i+r]=1;
    }
    for(i=1;i<=ni;i++)
    {
        fin>>y;
        for(j=1;j<=y;j++)
        {
            fin>>x;
            G[2*m+2*ns+2*r+1+i].pb(2*m+2*ns+1+x+r);
            G[2*m+2*ns+1+x+r].pb(2*m+2*ns+1+i+2*r);
            C[2*m+2*ns+1+x+r][2*m+2*ns+1+i+2*r]=1;

        }
        G[2*m+2*ns+1+i+2*r].pb(2*m+2*ns+1+i+2*r+ni);
        G[2*m+2*ns+1+i+2*r+ni].pb(2*m+2*ns+1+i+2*r);
        C[2*m+2*ns+1+i+2*r][2*m+2*ns+1+i+2*r+ni]=1;
        fin>>y;
        for(j=1;j<=y;j++)
        {
            fin>>x;
            G[2*m+1+2*ns+2*r+ni+i].pb(1+2*m+2*ns+2*r+2*ni+x);
            G[1+2*m+2*ns+2*r+2*ni+x].pb(2*m+1+2*ns+2*r+ni+i);
            C[2*m+1+2*ns+2*r+ni+i][2*m+1+2*ns+2*r+2*ni+x]=1;

        }

    }
    for(i=1;i<=c;i++)

    {G[2*m+1+2*ns+2*r+2*ni+i].pb(2*m+c+1+2*ns+2*r+2*ni+i);
     G[2*m+1+2*ns+2*r+2*ni+i+c].pb(2*m+1+2*ns+2*r+2*ni+i);
     C[2*m+1+2*ns+2*r+2*ni+i][2*m+1+2*ns+2*r+2*ni+i+c]=1;


    }
    for(i=1;i<=c;i++)
    {
        G[2*m+1+2*ns+2*r+2*ni+i+c].pb(sink);
        G[sink].pb(2*m+1+2*ns+2*r+2*ni+i+c);
        C[2*m+1+2*ns+2*r+2*ni+i+c][sink]=1;

    }
}

int main()
{
    cit();
    solve();
    return 0;
}