290 Gandaci Java

[•0x69]

Am bagat initial cuplaj maxim... tle + incorect. Am schimbat pe Hopcroft Karp, iau doar incorect. Fac cuplajul si stergerea vectorului. Omit ceva? Cei care au luat 0 si dupa 100 ce-ati facut sa scapati de incorect ?

Thx.

[•SpiderMan]

AR trebuie reevaluat si aici limita, sursa asta http://infoarena.ro/job_detail/613740 lua 100 inainte.

[•GavrilaVlad]

@Robert: Asta e a 3-a problema deja (celelalte 2: intersect, cuvinte2) la care zici ca limita e prea mica, desi tu nu luasesi 100 nici inainte de recalculare. Rog adminii sa verifice daca cei care semnaleaza limite eronate rezolvasera corect problema inainte.

[•SpiderMan]

Nu am luat eu, a luat prietenul meu si complexitatea e cam aceeasi ...
[PS] : Oricum trebuie recalculati multi timpi, poate ca un criteriu ar fi cea mai rea sursa care a luat 100 (in sens de timp) sa fie reevaluata (pt. fiecare pb) si daca ea nu ia 100 puncte, sa faca limita in asa fel incat sa ia 100.

[•pauldb]

Nu mi se pare bun criteriul. Trebuie sa ia 100 de puncte sursele care merita.

[•SpiderMan]

Am facut un cuplaj maxim care lua 100 in arhiva educationala .... ce altceva sa mai fac ... asa e si solutia oficiala ...

[•lucian666]

Buna Ziua.am facut la problema asta un Hopcroft Karp si nu iau decat 0 pct (incorect + 5 TLE) :'(vreo sugestie ceva.
Multumesc anticipat.

[•lucian666]

  :'(am verificat de 100 ori sursa si nu vad o greseala.rog un admin sa se uite peste sursa sa vada ce am gresit
Multumesc anticipat!

Cod:

#include<fstream>
#include<cstring>
#include<vector>

#define NN 10001
#define pb push_back

using namespace std;
ofstream out("java.out");

int  n,m,e,t,uz[NN],dr[NN],st[NN];
vector<int>G[NN];
typedef vector<int>:: iterator IT;

void read();
int pairup(int start);
int facuplaj();

int main()
{
	read();
	return 0;
	
	
}

int pairup(int start)
{
	if(uz[start])
		return 0;
	uz[start]=1;
		for(IT I=G[start].begin();I!=G[start].end();++I)
			if(!st[*I] || pairup(st[*I]) )
			{
				st[*I]=start;
				dr[start]=*I;
				return 1;
			}
			return 0;
}

int facuplaj()
{
	int ok=1;
	int cuplaj=0;
	while(ok)
	{
		ok=0;
		memset(uz,0,sizeof(uz));
		for(int i=1;i<=n;i++)
			if(!dr[i] && pairup(i))
			{
				++cuplaj;
				ok=1;
			}
	}
	return cuplaj;
}


void read()
{
	ifstream in("java.in");
	in>>t;
	while(t)
		
	{
		
	in>>m>>n>>e;
	for(int x,y,i=1;i<=e;i++)
	{
		in>>x>>y;
		G[x].pb(y);
		
	}
	
	facuplaj();
	int nrc=0;
	for(int i=1;i<=n;i++)
		if(dr[i])
			++nrc;
		out<<nrc<<'\n';
			//out<<i<<" "<<dr[i]<<" "<<'\n';

	t--;
	}
}

[•klamathix]

Cred ca ai incurcat m-ul cu n-ul la un moment dat. Mi se pare ca for-urile din cuplaj trebuie sa se duca pana la m.

[•lucian666]

Cred ca ai incurcat m-ul cu n-ul la un moment dat. Mi se pare ca for-urile din cuplaj trebuie sa se duca pana la m.

am modificat ,dar tot 0 pct iau  

[•freak93]

Nu te supara pe ce-ti zic acum, dar daca te-ai mai uitat pe forum ai vazut ca nu suntem tocmai pro acestei strategii "spuneti-mi unde am gresit". In general daca iti spunem noi ce ai gresit nu castigi prea mult.
Cel mai bine iti faci un backtracking, usor, scurt, si un generator de teste. Daca nu stii cum iti dau un exemplu. Cu ocazia asta inveti ceva pentru olimpiada.

[•lucian666]

  am reusit sa iau 60 pct:AM  8 TLE.folosesc Hopcroft Karp .ce as mai putea face sa reduc timpul?

Multumesc Anticipat!!!

[•PlayLikeNeverB4]

Desparte acel for din functia pairup() astfel incat prima data verifici daca il poti cupla simplu cu un vecin si a doua oara daca nu cumva poti recupla nodurile si apoi sa-l cuplezi cu vecinul. Deci sa faci doua for-uri separate pentru fiecare conditie.

[•lucian666]

Desparte acel for din functia pairup() astfel incat prima data verifici daca il poti cupla simplu cu un vecin si a doua oara daca nu cumva poti recupla nodurile si apoi sa-l cuplezi cu vecinul. Deci sa faci doua for-uri separate pentru fiecare conditie.

am incercat dar tot 60 iau

[•PlayLikeNeverB4]

N-ai facut ce am zis eu.

[•lucian666]

N-ai facut ce am zis eu.

Cod:

int pairup(int start)
{
	if(uz[start])
		return 0;
	uz[start]=1;
	for(IT I=G[start].begin();I!=G[start].end();++I)
			if(!dr[*I]  )
			{
				dr[*I]=start;
				st[start]=*I;
				
				return 1;
			}
	for(IT I=G[start].begin();I!=G[start].end();++I)
				if( pairup(dr[*I] ) )
				{
					dr[*I]=start;
					st[start]=*I;
					return 1;
				}
				
			return 0;
}

nu asa?

[•PlayLikeNeverB4]

Ba da. Scuze, n-am vazut in niciuna din sursele tale asta. Probabil va trebui si sa parsezi citirea pentru 100.

[•lucian666]

  am luat 100. de 2 ore tot incercam sa vad dc iau TLE ,dau eu trimiteam alta sursa .

[•Fayed]

Algoritmul meu este de a obtine un cuplaj maxim intre cercetatori(multime 1-m) si gandaci. Iau WA pe toate testele. In exemplu imi da bine. Am optimizat sa nu iau TLE sau MME. Imi bat capul de ore intregi si nu vad greseala. Ce am putut gresi aici ?
<code>
 #include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf

• .push_back(y);

       g

• = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st)
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g)
        Graf.assign(Graf.size()+1,0);
        memset(g,0,sizeof(g));
    --T;

    }
return 0;
}
</code>

[•SebiSebi]

Incearca sa resetezi toti vectorii folositi, inainte de a incepe un nou test. Succes!

[•Fayed]

Intr-adevar uitasem sa setez la 0 toti vectorii. Insa am facut aceasta modificare si iau 10 pcte. Iau si WA si TLE  pe unele teste.
Uite acum arata acum programul:

Cod:

#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        g[x] = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st[i])
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr[i]) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g[i])
        Graf[i].assign(Graf[i].size()+1,0);
        memset(g,0,sizeof(g));
        memset(dr,0,sizeof(dr));
        memset(st,0,sizeof(st));
        memset(vizitat,0,sizeof(vizitat));
    --T;

    }
return 0;
}

Editat de moderator: Foloseste tag-ul [ code ] [/ code ] cand postezi cod!

[•SebiSebi]

Inlocuieste asta :

Cod:

for(register int i=1;i<=m;++i)
        if(g)  Graf.assign(Graf.size()+1,0);

cu

Cod:

for(int i=1;i<=m;i++)
        Graf[i].clear();

[•Fayed]

Wow am luat 90. Inca iau TLE pe 2 teste.

[•SebiSebi]

Pentru 100 trebuie sa parsezi citirea. 

[•Fayed]

Da ma gandeam ca trebuie sa parsez si am luat 100. Mersi mult pentru cele 2 sfaturi cruciale. Mai ales ala cu Graf.clear am sa-l retin toata viata