Pagini recente » Cod sursa (job #1842401) | Cod sursa (job #1095253) | Cod sursa (job #2755594) | Borderou de evaluare (job #1283669) | Cod sursa (job #478012)
Cod sursa(job #478012)
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;
}