Pagini recente » Cod sursa (job #1172692) | Cod sursa (job #186463) | Cod sursa (job #1279179) | Cod sursa (job #283333) | Cod sursa (job #357418)
Cod sursa(job #357418)
#include <stdio.h>
#define DIM 1005
#define oo 1<<30-1
int c[DIM][DIM],f[DIM][DIM];
int q[DIM],t[DIM],sol[10*DIM];
int n,m,nrt;
void read ()
{
freopen ("critice.in","r",stdin);
int i,x,y,z;
scanf ("%d%d",&n,&m);
for (i=1; i<=m; ++i)
{
scanf ("%d%d%d",&x,&y,&z);
c[x][y]=c[y][x]=z;
}
}
int bf ()
{
int st,dr,i;
for (i=1; i<=n; ++i)
t[i]=0;
for (q[st=dr=1]=1; st<=dr; ++st)
for (i=1; i<=n; ++i)
if (!t[i] && c[q[st]][i]>f[q[st]][i])
{
t[i]=q[st];
q[++dr]=i;
if (i==n)
return 1;
}
return 0;
}
int min (int a,int b)
{
if (a<b)
return a;
return b;
}
void flux ()
{
int i,j,minim,flow;
for ( ; bf (); )
for (i=1; i<=n; ++i)
if (t[i]>0 && c[i][n]-f[i][n]>0)
{
minim=c[i][n]-f[i][n];
for (j=i; j!=1; j=t[j])
minim=min (minim,c[t[j]][j]-f[t[j]][j]);
f[i][n]+=minim;
f[n][i]-=minim;
for (j=i; j!=1; j=t[j])
{
f[t[j]][j]+=minim;
f[j][t[j]]-=minim;
}
}
}
void solve ()
{
freopen ("critice.in","r",stdin);
freopen ("critice.out","w",stdout);
int i,x,y,z;
flux ();
scanf ("%d%d",&n,&m);
for (i=1; i<=m; ++i)
{
scanf ("%d%d%d",&x,&y,&z);
c[x][y]=c[y][x]=z+1;
if (bf ())
sol[++nrt]=i;
c[x][y]=c[y][x]=z;
}
}
void print ()
{
int i;
printf ("%d\n",nrt);
for (i=1; i<=nrt; ++i)
printf ("%d\n",sol[i]);
}
int main ()
{
read ();
solve ();
print ();
return 0;
}