Cod sursa(job #2774516)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 11 septembrie 2021 19:33:52
Problema Cuplaj maxim de cost minim Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
int n,m,i,j,p,q,t,k,e,z,c[602][602],f[602][602],a[50001],b[50001],u[602],v[602][602],x[50001],w[50001],g[602];
int main()
{
	freopen("cmcm.in","r",stdin),freopen("cmcm.out","w",stdout),scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=k;++i)
    	scanf("%d%d%d",a+i,b+i,&j),c[a[i]][b[i]+n+1]=1,v[a[i]][b[i]+n+1]=j,v[b[i]+n+1][a[i]]=-j;
	for(i=1;i<=n;++i)
    	c[0][i]=1;
	for(i=n+2;i<=n+m+1;++i)
    	c[i][n+1]=1;
	while(1) {
		for(i=1;i<=n+m+1;++i)
            u[i]=0,g[i]=50001;
       	for(g[0]=p=w[0]=0,q=1;p<q;)
		   	for(t=w[p++],j=(t&&t<=n?(n+1):1),z=(t&&t<=n?(n+m+1):(n+1)),i=j;i<=z;++i)
                if(f[t][i]<c[t][i]&&g[i]>g[t]+v[t][i])
                    w[q++]=i,u[i]=t,g[i]=g[t]+v[t][i];
       	if(!u[n+1])
            break;
       	for(i=n+1;i;i=u[i])
            ++f[u[i]][i],--f[i][u[i]];
       	e+=g[n+1];
	}
	for(j=0,i=1;i<=k;++i)
        if(f[a[i]][b[i]+n+1]==1)
            x[j++]=i;
	printf("%d %d\n",j,e);
	for(i=0;i<j;i++)
       	printf("%d ",x[i]);
    return 0;
}