11248 - Frequency Hopping

[jah]

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, .

[sclo]

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.

[rio]

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

[shakil]

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; 
}

[baodog]

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));
                    }

[shakil]

baodog,
Again WA. Can you help.