Cod sursa(job #2323903)

Utilizator patcasrarespatcas rares danut patcasrares Data 19 ianuarie 2019 22:47:33
Problema Tribut Scor 0
Compilator cpp-64 Status done
Runda Arhiva ACM Marime 1.83 kb
#include<iostream>
#include<fstream>
#include<unordered_map>
#include<set>
#include<queue>
#include<algorithm>
#include<ctime>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("tribut.in");
ofstream fout("tribut.out");
const int DN=605;
int q[DN],nrq;
int t,n,m,cap[DN][DN],fl[DN][DN],nr,a[DN],f,g,z,vec[DN],b[DN],nrv,sistem[DN];
int flux,viz[DN],pr[DN];
vector<int>v[DN];
void add()
{
	v[f].pb(g);
	v[g].pb(f);
	cap[f][g]=z;
}
int vf()
{
	int nod;
	for(int i=1;i<=nr;i++)
		viz[i]=0;
	viz[1]=1;
	nrq=q[1]=1;
	for(int h=1;h<=nr;h++)
	{
		nod=q[h];
		//return 0;
		for(auto i:v[nod])
			if(fl[nod][i]!=cap[nod][i]&&!viz[i])
			{
				viz[i]=1;
				pr[i]=nod;
				nrq++;
				q[nrq]=nod;
			}
	}
	return viz[nr];
}
int main()
{
	fin>>t;
	while(t--)
	{
		fin>>n>>m;
		for(int i=1;i<=nr;i++)
			for(int j=1;j<=nr;j++)
				fl[i][j]=cap[i][j]=0;
        for(int i=1;i<=nr;i++)
            v[i].clear();
		nr=0;
		nr++;
		for(int i=1;i<=n;i++)
		{
			fin>>a[i];
			nr++;
			f=1;
			g=nr;
			z=a[i];
			vec[i]=i;
			add();
		}
		for(int i=1;i<=m;i++)
		{
			nr++;
			sistem[i]=nr;
			g=nr;
			fin>>nrv;
			fin>>b[i];
			for(int j=1;j<=nrv;j++)
			{
				fin>>f;
				f=vec[f];
				z=1e9;
				add();
			}
		}
		nr++;
		for(int i=1;i<=m;i++)
		{
			f=sistem[i];
			g=nr;
			z=b[i];
			add();
		}
		flux=0;
		while(vf())
		{
			for(auto i:v[nr])
			//if(viz[i])
			{
				pr[nr]=i;
				z=1e9;
				int nod=nr;
				while(nod!=1)
				{
					//if(nod==0)
					//	break;
					z=min(z,cap[pr[nod]][nod]-fl[pr[nod]][nod]);
					nod=pr[nod];
				}
				nod=nr;
				while(nod!=1)
				{
					//if(nod==0)
					//	break;
					fl[pr[nod]][nod]+=z;
					fl[nod][pr[nod]]-=z;
					nod=pr[nod];
				}
				flux+=z;
			}
		}
		fout<<flux<<'\n';
	}
}