一大牛的 網絡最大流 程序（POJ 1273 ）

和自己的比起來，感覺大牛的代碼要精悍的多啊。
代碼如下：
#include <stdio.h>
#include <string.h>
#define maxn 250
struct Map
{
?int f;
?int c;
}map[maxn][maxn];
int pre[maxn];
int q[maxn*maxn];
int v[maxn];
int N,M;
int s,t;
int abs( int x ){ return x > 0 ? x : -x ; }
int min( int x, int y ){ return? x < y ? x : y; }
void init()
{
?int i, S, E, C;
?memset( map, 0, sizeof(map) );
?for(i=0;i<N;i++)
?{
??scanf( "%d%d%d", &S, &E, &C );
??map[S][E].c += C;
?}?
}
void solve()
{
?int i,j;
?int head,tail;
?s = 1;
?t = M;
?while(true)
?{
??memset( pre, 0, sizeof(pre) );
??head = 0, tail = 1;
??q[0] = s;
??v[s] = 1000000000;
??pre[s] = s;
??while( head < tail && pre[t] == 0 )
??{
???i = q[head];
???for( j = 1; j <= M; j++ )
???{
????if( pre[j] == 0 )
????{
?????if( map[i][j].f < map[i][j].c )
??????pre[j] = i , q[tail++] = j , v[j] = min( v[i], map[i][j].c-map[i][j].f );
?????else if( map[j][i].f > 0 )
??????pre[j] = -i, q[tail++] = j , v[j] = min( v[i], map[j][i].f );
????}
??????????? }
???head++;
??}
??if( pre[t] == 0 )break;

??i = t;
??while( i != s )
??{
???j = abs( pre[i] );
???if( pre[i] > 0 )map[j][i].f += v[t];
???else map[i][j].f -= v[t];
???i = j;
??}
?}
?int ans = 0;
?for( i = 1; i <= M; i++ )ans += map[s][i].f;
?printf("%d\n",ans);
}
int main()
{
?while(scanf("%d%d",&N,&M)!=EOF)
?{
??init();
??solve();
?}
?return 0;
}

posted @ 2007-03-28 18:52 Barracuda 閱讀(2625) | 評論 (6) | 編輯 收藏

PKU 1273 第一次寫網絡最大流，居然AC了

第一次寫網絡最大流算法，居然做對了。
該算法要用到 Dijkstra 算法。
每次用Dijkstra算法求的一條可通過的路后，找出該路上面的最小的權值 MIN，然后將該路徑上的每條邊的權值 減去 MIN ，反方向的權值加 MIN （ 例如：e( v1, v2 ) 是路徑上面的一條邊，則Map[v1][v2] -= MIN, Map[v2][v1] += MIN ). 累計MIN， 其最后的值就是所要求的最大流。
當最后 在圖中找不到連接 1, n 兩點的路徑時，算法完畢。

//2019083 whitesea 1273 Accepted 224K 15MS C++ 1880B 2007-03-22 14:56:03
// PKU 1273 網絡最大流
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

#include<stdio.h>
#include<string.h>
#define MAX 210
int Map[MAX][MAX];
int n, M, SUM, Path[MAX], distance[MAX], Min;
int IN(){
    int i, x, y, d;
    if( scanf( "%d %d", &M, &n ) == EOF )return 0;  // M 是 邊的數目， n 是點的數目
    memset( Map, 0, sizeof( Map ) );
    for( i = 1; i <= M; i++ ){
        scanf( "%d %d %d", &x, &y, &d );   // 點x 到點y流量為 d
        Map[x][y] += d;
    }
    return 1;
}
void Dijkstra(){
    int mindis, i, j, u, s[MAX];
    for( i = 1; i <= n; i++ ){
        distance[i] = Map[1][i];
        s[i] = 0;
       
        if( i != 1 && distance[i] > 0 )Path[i] = 1;
        else Path[i] = -1;
    }
    s[1] = 1;
    for( i = 2; i <= n; i++ ){
        mindis = 0;
        for( j = 1; j <= n; j++ ){
            if( s[j] == 0 && distance[j] > mindis ){
                u = j;
                mindis = distance[j];
            }
        }
        if( mindis == 0 )return;
        s[u] = 1;
        for( j = 1; j <= n; j++ ){
            if( s[j] == 0 && Map[u][j] > 0 && distance[u] + Map[u][j] > distance[j] ){
                distance[j] = distance[u] + Map[u][j];
                Path[j] = u;
            }
        }
    }
}

void Find(){
    int s, t;
    Min = 2000000000;
    s = n;
    t = Path[n];
    while( t != -1 ){
        if( Map[t][s] < Min )Min = Map[t][s];
        s = t;
        t = Path[t];
    }
}

void Change(){
    int s, t;
    s = n;
    t = Path[n];
    while( t != -1 ){
        Map[t][s] -= Min;
        Map[s][t] += Min;
        s = t;
        t = Path[t];
    }
}

void SOLVE(){
    int i, j, k;
    SUM = 0;
    while( 1 ){
        Dijkstra();
        if( Path[n] == -1 )return;
        Find();
        SUM += Min;
        Change();
    }
}

void OUT(){
    printf( "%d\n", SUM );
}

int main(){
    while( IN() ){
       
        SOLVE();
        OUT();
    }
    return 0;
}

posted @ 2007-03-22 15:18 Barracuda 閱讀(2044) | 評論 (8) | 編輯 收藏

做PKU做ACM 滿200題紀念帖

??????? 做ACM 已經有快一年了，終于在PKU做滿200題， 發帖紀念下，鼓勵自己再接再厲。這一年發生的變化還真大啊，一不小心從一個新生變成了老生，從一個新手變成了老隊員。想起來這一年來，感覺收獲還是很大的。在這里我要特別感謝XC?? Azg? Taney? Stone CB? ,他們給了我幫助與鼓勵，也要感謝我的隊友Lvyun Hailer，他們給了我很多的幫助。在做ACM 這個方面，我們學校一直很差，在06~07的全國三個賽區都摻敗而歸。現在我得努力，我的隊友得努力，CUG 的ACMER 都得努力。讓我們來把CUG 的ACM 做好， 努力吧，加油吧！

posted @ 2007-03-17 17:34 Barracuda 閱讀(481) | 評論 (1) | 編輯 收藏