poj Budget

poj Budget

Budget

建圖好題，不知道為什麼提交一直TLE。然後，該了幾次，看了別人的普通網絡流都過了。我認為可能是卡DINIC的某些部分吧。這題就是一道普通的上下界最小流。

建圖麻煩，所以說一下建圖吧。

建圖可以象方格取數的方法一樣，把行列拆了，然後最後讓行總和或列總和等於題目的要求。這樣在滿足一下題目的上下界要求後圖就建好了。跑兩邊最大流就Ok了。

因為，一直TLE所以不給出完整代碼，只給出建圖過程。囧。。。

int main()
{
    int T;
    scanf("%d\n",&T);
    while(T--){
        char ope[5];
        int x,y,c;

        scanf("%d%d\n",&N,&M);

        init();
        memset(in,0,sizeof(in));

        for(int i = 1;i <= N;++i){
            for(int j = 1;j <= M;++j){
                B[i][j] = 0;
                C[i][j] = INF;
            }
        }

        for(int i = 1;i <= N;++i){   //行
            scanf("%d",&c);

            addEdge(ss,i,0);
            in[ss] -= c;
            in[i] += c;
        }

        for(int j = 1;j <= M;++j){  //列
            scanf("%d",&c);

            addEdge(j+N,tt,0);
            in[j + N] -= c;
            in[tt] += c;
        }

        int cas;
        scanf("%d",&cas);
        while(cas--){
            scanf("%d%d%s%d",&x,&y,ope,&c);
            if(c < 0){
                flag = true;
            }
            int x1,x2,y1,y2;
            x1 = x2 = x;
            y1 = y2 = y;
            if(!x) x1 = 1,x2 = N;
            if(!y) y1 = 1,y2 = M;
            for(int i = x1;i <= x2;++i){
                for(int j = y1;j <= y2;++j){
                    if(ope[0] == '=')
                        B[i][j] = C[i][j] = c;
                    else if(ope[0] == '>')
                        B[i][j] = max(B[i][j],c + 1);
                    else
                        C[i][j] = min(C[i][j],c - 1);
                    if(C[i][j] < B[i][j])
                        flag = false;
                }
            }
        }

        if(flag){
            puts("IMPOSSIBLE");
            if(T)puts("");
            continue;
        }

         //建圖
        for(int i = 1;i <= N;++i){
            for(int j = 1;j <= M;++j){
                addEdge(i,j + N,C[i][j] - B[i][j]);
                in[i] -= B[i][j];
                in[j+N] += B[i][j];
            }
        }

        int sum = 0;
        for(int i = 1;i <= tt;++i){
            if(in[i] > 0){
               sum += in[i];
               addEdge(src,i,in[i]);
            }
            if(in[i] < 0){
               addEdge(i,sink,-in[i]);
            }
        }

        addEdge(tt,ss,INF);      ///!!!!!!!!!! tt --> ss 不要在粗心了！！!   T_T
        int flow = maxFlow(src,sink);

        if(flow != sum){
            puts("IMPOSSIBLE");
        } else {
           maxFlow(src,sink);
        }
        if(T)puts("");
    }
    return 0;
}