Pagini recente » Cod sursa (job #1781604) | Cod sursa (job #2963108) | Cod sursa (job #2981101) | Cod sursa (job #759498) | Cod sursa (job #391804)
Cod sursa(job #391804)
#include <stdio.h>
#include <queue>
using namespace std;
struct mat{int cs;char cp;}a[602][602];
char iq[603];
int S,D,d[603],t[603];
void bel(){
queue<int> Q; int nod,i;
memset(d,127,sizeof(d));
d[S]=0;
Q.push(S);iq[S]=1;
while (!Q.empty()){
nod=Q.front(); Q.pop(); iq[nod]=0;
for (i=0;i<=D;++i)
if (a[nod][i].cp) if (d[nod]+a[nod][i].cs < d[i]){
d[i]=d[nod]+a[nod][i].cs; t[i]=nod;
if (!iq[i]){ Q.push(i); iq[i]=1; }
}
}
}
int main(){
freopen("cmcm.in","r",stdin); freopen("cmcm.out","w",stdout);
int n,m,p,i,j,x,y,z,aux,cost=0,fl=0,path[603];
scanf("%d %d %d",&n,&m,&p);
S=0;D=n+m+1;
for (i=1;i<=p;++i){ scanf ("%d %d %d",&x,&y,&z); a[x][n+y].cs=z; a[x][n+y].cp=1; a[n+y][x].cs=-z;}
for (i=1;i<=n;i++){a[0][i].cs=1;a[0][i].cp=1;a[i][0].cs=-1;}
for (i=n+1;i<D;i++){a[i][D].cs=1;a[i][D].cp=1;a[D][i].cs=-1;}
do{
bel();
j=0;aux=D;
if(d[D]==2139062143)break;
while (aux!=0){ path[++j] = aux ; aux=t[aux] ; }
path[++j]=0;
if (j<4)break;
for (i=1;i<j;++i){a[path[i+1]][path[i]].cp=0; a[path[i]][path[i+1]].cp=1; }
cost+=d[D];
fl++;
}while(j);
printf("%d %d\n",fl,cost-2*fl);
return 0;
}