OJ Board

Posted: **Wed Aug 01, 2007 3:27 am**

Hi,

I haven't tried the problem yet but I have seen a possible approach in the book Network flows (ahuja,magnanti,orlin) which is called Highest-label preflow-push. I think I will wait until uva's migration, I'm not a sadomasochist,

.

Posted: **Wed Aug 01, 2007 3:31 am**

That is precisely what I've implemented.
Now I got WA at 3.2 secs, probably I've wrecked my implementation. I better check it against another maxflow problem on UVa.

Edit: I have 2 versions of my push-relabel algorithrm:
version 1 is done using LIFO to select active nodes. It is correct but it tle because implementing the gap heuristic may be too expensive.

version 2 is done using high to low selection of active node. It is easy to implement the gap heuristic, but my implementation seems to be wrong, and it fails every other maxflow problems I tried on UVa.

Posted: **Thu Aug 02, 2007 10:04 am**

Finally got AC after almost 100 submissions

I implemented push-relabel algorithm using FIFO with global relabeling.
I didn't use gap heuristic this time.
For only calculating the minimum cut, my program needs about 0.54 seconds for all test cases.

----
Rio

Posted: **Tue Sep 25, 2007 5:33 pm**

Why WA.Please help.Please give me some test case which fail my program.Thanks in advance.

Code: Select all

#include<stdio.h> 
#include<string.h> 
#define NN 109 
int cap[NN][NN],deg[NN],adj[NN][NN],cap_save[NN][NN]; 
int q[NN],prev[NN],CC,CCC; 

int dinic(int n,int s,int t) 
{ 
int flow =0,u,v,z,i; 
while(true) 
{ 
memset(prev,-1,sizeof(prev)); 

int qf=0,qb=0; 
prev[q[qb++]=s]=-2; 
while(qb>qf&&prev[t]==-1) 
for(u = q[qf++],i=0,v;i<deg[u];i++) 
if(prev[v=adj[u][i]]==-1&&cap[u][v]) 
prev[q[qb++]=v]=u; 

if(prev[t]==-1) 
break; 

for( z=0;z<n;z++) 
if(cap[z][t]&&prev[z]!=-1) 
{ 
int bot = cap[z][t]; 


for( v=z,u=prev[v];u>=0;v=u,u=prev[v]) 
if(bot>cap[u][v]) 
bot=cap[u][v]; 

if(!bot) 
continue; 

cap[z][t]-=bot; 
cap[t][z]+=bot; 

for( v=z,u=prev[v];u>=0;v=u,u=prev[v]) 
{ 
cap[u][v]-=bot; 
cap[v][u]+=bot; 
} 

flow+=bot; 
if(flow>=CC) 
break; 
} 
if(flow>=CC) 
break; 
} 

return flow; 

} 

int make(int n,int s,int t,int cap[109][109]) 
{ 
int flow =0,u,v,z,i; 
while(true) 
{ 
memset(prev,-1,sizeof(prev)); 

int qf=0,qb=0; 
prev[q[qb++]=s]=-2; 
while(qb>qf&&prev[t]==-1) 
for(u = q[qf++],i=0,v;i<deg[u];i++) 
if(prev[v=adj[u][i]]==-1&&cap[u][v]) 
prev[q[qb++]=v]=u; 

if(prev[t]==-1) 
break; 

for( z=0;z<n;z++) 
if(cap[z][t]&&prev[z]!=-1) 
{ 
int bot = cap[z][t]; 


for( v=z,u=prev[v];u>=0;v=u,u=prev[v]) 
if(bot>cap[u][v]) 
bot=cap[u][v]; 

if(!bot) 
continue; 

cap[z][t]-=bot; 
cap[t][z]+=bot; 

for( v=z,u=prev[v];u>=0;v=u,u=prev[v]) 
{ 
cap[u][v]-=bot; 
cap[v][u]+=bot; 
} 

flow+=bot; 
if(flow>=CC-CCC) 
break; 
} 
if(flow>=CC-CCC) 
break; 
} 

return flow; 

} 


int main() 
{ 

int n,s,t,m,u,v,c,test=0,flow,sa[109][109],i,j,k,in=0,flag; 

while(1) 
{ 
scanf("%d %d %d",&n,&m,&CC); 
if(n==0&&m==0&&CC==0) 
break; 
memset(cap,0,sizeof(cap)); 
memset(sa,0,sizeof(sa)); 
s=0; 
t=n-1; 
while(m--) 
{ 
scanf("%d %d %d",&u,&v,&c); 
cap[u-1][v-1]+=c; 
sa[u-1][v-1]=cap[u-1][v-1]; 
cap[v-1][u-1]+=c; 
} 
memset(deg,0,sizeof(deg)); 
for(u=0;u<n;u++) 
for(v=0;v<n;v++) 
if(cap[u][v]) 
adj[u][deg[u]++]=v; 

test++; 

flow=dinic(n,s,t); 
in++; 
printf("Case %d: ",in); 
if(flow>=CC) 
printf("possible\n"); 
else 
{ 
CCC=flow; 
flag=0; 
memcpy(cap_save,cap,sizeof(cap));
for(i=0;i<n;i++) 
for(j=0;j<n;j++) 
if(sa[i][j]!=0&&cap[i][j]==0) 
{ 
cap[i][j]=CC; 
k=make(n,s,t,cap); 
if(flow+k>=CC) 
{ if(flag==0) 
{printf("possible option:(%d,%d)",i+1,j+1); 
flag=1;} 
else 
printf(",(%d,%d)",i+1,j+1); 
} 
cap[i][j]=0; 
 memcpy(cap,cap_save,sizeof(cap));
} 

if(flag==0) 
printf("not possible"); 
printf("\n"); 
} 
} 
return 0; 
}

Posted: **Wed Oct 10, 2007 6:59 am**

You need to restore the remaining capacity after checking each
edge (otherwise it's not independent).

Like this:

Code: Select all

            memcpy(cap_save,cap,sizeof(cap));
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    if(sa[i][j]!=0&&cap[i][j]==0)
                    {
                        cap[i][j]=CC;
                        k=make(n,s,t,cap);
                        // cout << k << endl;
                        if(flow+k>=CC)
                        {
                            if(flag==0)
                            {
                                printf("possible option:(%d,%d)",i+1,j+1);
                                flag=1;
                            }
                            else
                                printf(",(%d,%d)",i+1,j+1);
                        }
                        cap[i][j]=0;
                        memcpy(cap,cap_save,sizeof(cap));
                    }

Posted: **Fri Nov 02, 2007 8:31 pm**

baodog,
Again WA. Can you help.

OJ Board

11248 - Frequency Hopping

Highest-label preflow-push algorithm