Cod sursa(job #2323900)

Utilizator patcasrarespatcas rares danut patcasrares Data 19 ianuarie 2019 22:43:46
Problema Tribut Scor 0
Compilator cpp-64 Status done
Runda Arhiva ACM Marime 2.26 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;
FILE* fin=fopen("tribut.in","r");
const unsigned maxb=30000192;
char buf[maxb];
unsigned ptr=maxb-1;
inline unsigned getint()
{
    unsigned nr=0;
    while(buf[ptr]<'0'||buf[ptr]>'9')
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    while(buf[ptr]>='0'&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    return nr;
}
ofstream fout("tribut.out");
const int DN=605;
queue<int>q;
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;
	q.push(1);
	while(!q.empty())
	{
		nod=q.front();
		q.pop();
		//return 0;
		for(auto i:v[nod])
			if(fl[nod][i]!=cap[nod][i]&&!viz[i])
			{
				viz[i]=1;
				pr[i]=nod;
				q.push(i);
			}
	}
	return viz[nr];
}
int main()
{
	t=getint();
	while(t--)
	{
		n=getint();
		m=getint();
		for(int i=1;i<DN;i++)
			for(int j=1;j<DN;j++)
				fl[i][j]=cap[i][j]=0;
        for(int i=1;i<DN;i++)
            v[i].clear();
		nr=0;
		nr++;
		for(int i=1;i<=n;i++)
		{
			a[i]=getint();
			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;
			nrv=getint();
			b[i]=getint();
			for(int j=1;j<=nrv;j++)
			{
				f=getint();
				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';
	}
}