b014 - D.工廠生產問題

ForTest

題目：http://judge.tnfsh.tn.edu.tw:8080/ShowProblem?problemid=b014

我這題是想說用網路流爆下去 不過NA了
然後Code上方是某judge的模板
不清楚錯在哪裡m(_ _)m


/**********************************************************************************/  
/*  Problem: b014 "D.工廠生產問題" from 2008 校內初選                             */  
/*  Language: C++                                                                 */  
/*  Result: NA (7 / 21) on ZeroJudge                                              */  
/*  Author: ForTest at 2014-03-24 14:23:06                                        */  
/**********************************************************************************/  
  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <vector>  
#include <algorithm>  
#include <map>  
#include <queue>  
  
using namespace std;  
  
#define F(a,b) for(int a=0;a<b;++a)  
typedef long long LL;  
  
#define FN 5010 //點數  
#define FM 500010 //邊數  
#define INF 0x7fffffff //視為無限大的值  
// E 是弧的 struct  
// k 是該弧所連到的點  
// c 是該弧的剩餘流量  
// 其中 es[2k] 和 es[2k+1] 儲存的弧一定是連相同兩點但方向相反的弧  
// m 是對於編號為 id 的弧我們可知它是由點 es[id^1].k 連出去的  
// 用此方法存弧可縮減記憶體使用量  
struct E {  
    LL k,c;  
    E(){}  
    E( LL _k, LL _c ):k(_k),c(_c){}  
} es[FM*2];  
  
struct Flow {  
    // n 為點數，m 為弧數  
    // dis 為從源點藉由剩餘流量非零的弧到某點的最短距  
    // e 記錄每個點連出去的弧的編號  
    // 此程式碼限定源點為 0,匯點為 n-1  
  
    LL n,m,dis[FN],ptr[FN];  
    LL qq[FN],qr,ql;  
    vector<LL> e[FN];  
    // init 為初始化函數  
    void init( LL _n ) {  
        n=_n; m=0;  
        for ( int i=0; i<n; i++ ) e[i]=vector<LL>();  
    }  
    // 在網路流模型添加一條由 a 到 b 且流量限制為 c 的弧  
    void add( LL a, LL b, LL c ) {  
        e[a].push_back(m); es[m]=E(b,c); m++;  
        e[b].push_back(m); es[m]=E(a,0); m++;  
    }  
    // 使用 bfs 得到 dis 陣列的值  
    bool BFS() {  
        memset(dis,-1,sizeof dis);  
        ql=qr=0;  
        qq[qr++]=0;  
        dis[0]=0;  
        while ( ql!=qr && dis[n-1]==-1 ) {  
            LL p=qq[ql++];  
            for(int i=0;i < (int)e[p].size(); i++) {  
                E ee=es[ e[p][i] ];  
                if ( ee.c==0 || dis[ee.k]!=-1 ) continue;  
                dis[ee.k]=dis[p]+1;  
                qq[qr++]=ee.k;  
            }  
        }  
        return dis[n-1]!=-1;  
    }  
    // 回傳在分層圖中，找出一條從 p 出發流量不超過 c 的增廣路並回傳值  
    LL go( LL p, LL c ) {  
        if ( p==n-1 ) return c;  
        LL tmp;  
        // 若從 i=0 開始，也就是每次呼叫函式是都檢查該點所有連出的弧  
        // 此演算法的時間複雜度仍會和 Edmonds-Karps Algorithm 一樣  
  
        for(int i=ptr[p]; i<(int)e[p].size(); i++) {  
            E &ee=es[e[p][i]];  
            // 若剩餘流量為零或該弧不為分層圖上的弧就跳過  
            if ( ee.c==0 || dis[p]+1!=dis[ee.k] ) continue;  
            tmp=go(ee.k,min(c,ee.c));  
            // 若能藉由該弧流到匯點，就回傳結果  
            // 並設 ptr[p]=i 代表下次使用此函式直接從第 ptr[p] 個弧檢查就行了  
            // 於是每條弧至多都只會出現一次檢查時沿該弧找不到增廣路的情形  
            // 失誤的次數為 O(m), 而每次找到增廣路的弧數為 O(n)  
            // 於是能確保每次在分層圖上找到所有最短增廣路的時間複雜度為 O(nm)  
  
            if(tmp != 0){  
                ee.c-=tmp; es[e[p][i]^1].c+=tmp;  
                ptr[p]=i;  
                return tmp;  
            }  
        }  
        ptr[p] = (int)e[p].size();  
        return 0;  
    }  
    // 此為求最大流的主函式  
    LL maxflow() {  
        LL ret=0; // 儲存答案的變數  
  
        // 每次要找所有最短增廣路之前  
        // 先使用 bfs 以便知道哪些弧是分層圖上的弧  
        // 並當已經無法從源點到匯點時結束 while 迴圈  
        while ( BFS() ){  
            for(int i=0;i<n;i++)ptr[i]=0;  
  
            // 以 bfs 得到分層圖後一直找弧全在分層圖上的增廣路直到找不到為止  
            // 由於每次找到增廣路後分層圖上至少會有一條弧剩餘流量減至 0  
            // 故至多找到 O(m) 條增廣路  
            while(true){  
                LL tmp=go(0,INF);  
                if(tmp)ret+=tmp;  
                else break;  
            }  
        }  
        return ret;  
    }  
} flow;  
int main(){  
    LL n;  
    while(~scanf("%lld",&n)){  
        flow.init(n+2);  
        LL p[n+1];  
        bool in[n+1],out[n+1];  
        memset(in,0,sizeof in);  
        memset(out,0,sizeof out);  
        F(i,n) scanf("%lld",&p[i+1]);  
        LL m;  
        scanf("%lld",&m);  
        while(m--){  
            LL a,b;  
            scanf("%lld%lld",&a,&b);  
            flow.add(a,b,p[a]);  
            out[a] = 1;  
            in[b] = 1;  
        }  
        F(i,n){  
            if(!in[i+1]) flow.add(0,i+1,0x7fffffff);  
            if(!out[i+1])flow.add(i+1,n+1,p[i+1]);  
        }  
        printf("%lld\n",flow.maxflow());  
    }  
    return 0;  
}