#5111: 820 - Internet Bandwidth


a13032002 (國王的子民(23rd))

學校 : 國立新竹高級中學
編號 : 7254
來源 : [140.112.243.121]
最後登入時間 :
2012-06-15 16:07:06
d667. 00820 - Internet Bandwidth -- UVa820 | From: [140.112.240.134] | 發表日期 : 2011-05-11 16:57

第一次實作最大流,結果WA

不知道哪裡錯了或沒注意到

麻煩大大們幫我看一下  感激

 

#include <cstdio>
#include <queue>
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;

int E[100][100];
int E_C[100];
int R[100][100];
int BFS(int s,int t,int P[]){
    int F[100];
    bool fg[100] = {0};
    queue<int> q;
    fg[s] = 1;
    F[s] = 2e9;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i = 0,u;i < E_C[v];i++){
            u = E[v][i];
            if(!fg[u] && R[v][u] > 0){
                fg[u] = 1;
                F[u] = min(F[v],R[v][u]);
                P[u] = v;
                if(u == t)
                    return F[u];
                q.push(u);
            }
        }
    }
    return 0;
}



int main(){
    int Q = 1;
    int N;
    while(1){
        scanf("%d",&N);
        if(N == 0)return 0;
        for(int i = 0;i < N;i++)
            for(int j = 0;j < N;j++)
                R[i][j] = 0;

        for(int i = 0;i < N;i++)
            E_C[i] = 0;

        int S,T,CC;
        scanf("%d %d %d",&S,&T,&CC);
        for(int i = 0,u,v,w;i < CC; i++){
            scanf("%d %d %d",&u,&v,&w);
            u--;
            v--;
            R[u][v] += w;
            R[v][u] += w;
            E[u][E_C[u]] = v ;
            E[v][E_C[v]] = u;
            E_C[u]++;
            E_C[v]++;
        }
        int Ans = 0;
        int tt;
        int P[100];
        S--;
        T--;
        while(1){
            tt = BFS(S,T,P);
            if (tt == 0)break;
            for(int v = T;v != S;v = P[v]){
                R[P[v]][v] -= tt;
                R[v][P[v]] += tt;
            }
            Ans += tt;
        }
        printf("Network %d\nThe bandwidth is %d.\n\n",Q++,Ans);
    }
}

 
#5114: Re:820 - Internet Bandwidth


pcsh710742 (ms0472904)

學校 :
編號 : 2494
來源 : [1.34.10.217]
最後登入時間 :
2015-08-22 19:29:41
d667. 00820 - Internet Bandwidth -- UVa820 | From: [61.228.149.134] | 發表日期 : 2011-05-14 19:00

第一次實作最大流,結果WA

不知道哪裡錯了或沒注意到

麻煩大大們幫我看一下  感激

 

#include
#include
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;

int E[100][100];
int E_C[100];
int R[100][100];
int BFS(int s,int t,int P[]){
    int F[100];
    bool fg[100] = {0};
    queue q;
    fg[s] = 1;
    F[s] = 2e9;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i = 0,u;i < E_C[v];i++){
            u = E[v][i];
            if(!fg[u] && R[v][u] > 0){
                fg[u] = 1;
                F[u] = min(F[v],R[v][u]);
                P[u] = v;
                if(u == t)
                    return F[u];
                q.push(u);
            }
        }
    }
    return 0;
}



int main(){
    int Q = 1;
    int N;
    while(1){
        scanf("%d",&N);
        if(N == 0)return 0;
        for(int i = 0;i < N;i++)
            for(int j = 0;j < N;j++)
                R[i][j] = 0;

        for(int i = 0;i < N;i++)
            E_C[i] = 0;

        int S,T,CC;
        scanf("%d %d %d",&S,&T,&CC);
        for(int i = 0,u,v,w;i < CC; i++){
            scanf("%d %d %d",&u,&v,&w);
            u--;
            v--;
            R[u][v] += w;
            R[v][u] += w;
            E[u][E_C[u]] = v ;
            E[v][E_C[v]] = u;
            E_C[u]++;
            E_C[v]++;
        }
        int Ans = 0;
        int tt;
        int P[100];
        S--;
        T--;
        while(1){
            tt = BFS(S,T,P);
            if (tt == 0)break;
            for(int v = T;v != S;v = P[v]){
                R[P[v]][v] -= tt;
                R[v][P[v]] += tt;
            }
            Ans += tt;
        }
        printf("Network %d\nThe bandwidth is %d.\n\n",Q++,Ans);
    }
}

貌似是E那個陣列的第二個維度開太小了,

我只能說這題的測資質真的不是普通的陰險= ="

 
ZeroJudge Forum