Pagini recente » Cod sursa (job #403668) | Cod sursa (job #2018776) | Cod sursa (job #1551545) | Cod sursa (job #1464095) | Cod sursa (job #357419)
Cod sursa(job #357419)
#include <stdio.h>
#define DIM 1005
#define oo 1<<30-1
struct nod {int x;
nod *urm;} *lst[DIM];
int c[DIM][DIM],f[DIM][DIM];
int q[DIM],t[DIM],sol[10*DIM];
int n,m,nrt;
void add (int a,int b)
{
nod *p=new nod;
p->x=a;
p->urm=lst[b];
lst[b]=p;
}
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;
add (x,y);
add (y,x);
}
}
int bf ()
{
int st,dr,i;
nod *p;
for (i=1; i<=n; ++i)
t[i]=0;
for (q[st=dr=1]=1; st<=dr; ++st)
for (p=lst[q[st]]; p; p=p->urm)
if (!t[p->x] && c[q[st]][p->x]>f[q[st]][p->x])
{
t[p->x]=q[st];
q[++dr]=p->x;
}
return t[n];
}
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;
}