UVa11506 - Angry Programmer(ISAP)

#include <cstdio>  #include <queue>  #include <cstring>  #include <algorithm>  usingnamespacestd;  
constintN=110;  
constintINF=0x3f3f3f3f;  
intm, w;   
intd[N], num[N];  
intcur[N], p[N];
intcap[N][N], flow[N][N];
boolinput();  
voidrev_bfs();
intmax_flow();
intAugment();
intRetreat(int&i);
intmain()  
{  
#ifndef ONLINE_JUDGE  freopen("d:\\OJ\\uva_in.txt", "r", stdin);  
#endif  while (input()) {  
intans=max_flow();
printf("%d\n", ans);  
    }  
return0;  
}  
boolinput()  
{  
if (scanf("%d%d", &m, &w) !=2|| (m==0&&w==0)) returnfalse;  
intu, v, c;  
memset(cap, 0x00, sizeof(cap));
memset(flow, 0x00, sizeof(flow));
for (inti=0; i<m-2; i++) {  
scanf("%d%d", &u, &c);  
cap[u][u+m] =cap[u+m][u] =c;
    }  
for (inti=0; i<w; i++) {  
scanf("%d%d%d", &u, &v, &c);  
if (u==1&&v==m) {
cap[u][v] =cap[v][u] =c;
        } elseif (u==1&&v!=m) {  
cap[u][v] =c;
cap[v+m][u] =c;
        } elseif (u==m&&v==1) {  
cap[u][v] =cap[v][u] =c;
        } elseif (u==m&&v!=1) {   
cap[u][v] =c;
cap[v+m][u] =c;
        } else {  
cap[u+m][v] =c;
cap[v+m][u] =c;
        }  
    }  
returntrue;  
}  
voidrev_bfs()
{
queue<int>q;
memset(num, 0x00, sizeof(num));
for (inti=1; i<=2*m; i++) {
num[d[i] =2*m]++;
    }
num[2*m]--;
d[m] =0;
num[0]++;
q.push(m);
while (!q.empty()) {
intv=q.front(); q.pop();
for (intu=1; u<2*m; u++) {
if (d[u] <2*m||cap[u][v] ==0) continue;
q.push(u);
num[d[u]]--;
d[u] =d[v] +1;
num[d[u]]++;
        }
    }
}
intmax_flow()
{
intf=0, i, j;
memset(d, 0x00, sizeof(d));
memset(p, 0x00, sizeof(p));
rev_bfs();
for (i=1; i<=2*m; i++) cur[i] =1;
i=1;
for (; d[1] <2*m; )
    {
for (j=cur[i]; j<=2*m; j++) {
if (cap[i][j] >flow[i][j] &&d[i] ==d[j] +1) break;
        }
if (j<=2*m) {
cur[i] =j;
p[j] =i;
i=j;
if (i==m) {
f+=Augment();
i=1;
            }
        } else {
cur[i] =1;
if (Retreat(i) ==0) break;
        }
    }
returnf;
}
intAugment()
{
intans=INF;
for (inti=m, j=p[i]; i!=1; i=j, j=p[j]) {
ans=min(ans, cap[j][i] -flow[j][i]);
    }
for (inti=m,  j=p[i]; i!=1; i=j, j=p[j]) {
flow[j][i] +=ans;
flow[i][j] -=ans;
    }
returnans;
}
intRetreat(int&i)
{
intmind=2*m-1;
for (intj=1; j<=2*m; j++) {
if (cap[i][j] >flow[i][j] &&d[j] <mind) {
mind=d[j];
        }
    }
inttmp=d[i];
num[d[i]]--;
d[i] =mind+1;
num[d[i]]++;
if (i!=1) i=p[i];
returnnum[tmp];
}