UvaL-7670 上下界可行费用流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define P 55
#define N 2050
#define INF (1<<30)
 
using namespace std;
 
int n,m,S,T,ss,tt,cnt=1,tot=0;
int head[N],d[N],p[N],qlc[P],qrc[P],qlr[P],qrr[P];
int map[P][P],sc[P],sr[P],r[P],c[P],dis[N];
int ans,tl;
struct Edge{ int a,b,v,cost,next; }e[10*N];
void add(int a,int b,int v,int cost) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].v = v;
    e[cnt].cost = cost;
    e[cnt].next = head[a];
    head[a] = cnt;
}
 
inline void add_Node(int a,int b,int vl,int vr,int cost) {
    //printf("Node %d %d %d %d
",a,b,vl,vr);
    d[a] -= vl; d[b] += vl;
    add(a,b,vr-vl,cost); add(b,a,0,-cost);
}
void paul() {
    ss = tot+1; tt = tot+2;
    for (int _=1;_<=tot;_++) {
        if (d[_] < 0) add(_,tt,-d[_],0) , add(tt,_,0,0);
        if (d[_] > 0) add(ss,_, d[_],0) , add(_,ss,0,0); 
    }
}
 
#define cp e[i].v
#define B e[i].b
 
bool SPFA() {
    bool flag = false;
    memset(p,0,sizeof(p));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[ss] = 0;
    queue<int> q; q.push(ss);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == tt) flag = true; 
        for (int i=head[u];i;i=e[i].next)
            if (cp > 0 && dis[u] + e[i].cost < dis[B]) {
                dis[B] = dis[u] + e[i].cost;
                p[B] = i;
                q.push(B);
            } 
    }
    return flag;
}
 
void mcf() {
    int g = p[tt] , flow = INF;
    while (g) {
        flow = min(flow , e[g].v);
        g = p[ e[g].a ];
    }
    g = p[tt];
    while (g) {
        e[g  ].v -= flow;
        e[g^1].v += flow;
        ans += e[g].cost * flow;
        g = p[ e[g].a ];
    }
    tl += flow;
}
 
void init() {
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    memset(d,0,sizeof(d));
    
    //memset(qlr,0,sizeof(qlr));
    //memset(qrr,0,sizeof(qrr));
    //memset(qlc,0,sizeof(qlc));
    //memset(qrc,0,sizeof(qrc));
    
    memset(sc,0,sizeof(sc));
    memset(sr,0,sizeof(sr));
    memset(c,0,sizeof(c));
    memset(r,0,sizeof(r));
    memset(map,0,sizeof(map));
    cnt = 1; tot = 0;
    S = ++tot; T = ++tot; add_Node(T,S,0,INF,0);
    ans = tl = 0;
}
 
 
int main() {    
    #ifndef ONLINE_JUDGE
        freopen("5.in","r",stdin);
    #endif
    while (~scanf("%d",&n)) {
        init();
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) {
            scanf("%d",&map[i][j]);
            if (map[i][j]) sr[i]++ ,sc[j]++;
        }
        for (int i=1;i<=n;i++) r[i] = ++tot , c[i] = ++tot;
        for (int i=1;i<=n;i++) {
            scanf("%d%d",&qlr[i],&qrr[i]);
            add_Node(S,r[i],sr[i],sr[i],0); //³¬¼¶Ô´ --> µÚiÐÐ   
            add_Node(r[i],T,qlr[i],qrr[i],0);       //µÚiÐÐ  --> ³¬¼¶»ã 
        }
        for (int i=1;i<=n;i++) {
            scanf("%d%d",&qlc[i],&qrc[i]);
            add_Node(S,c[i],sc[i],sc[i],0); //³¬¼¶Ô´ --> µÚiÁÐ 
            add_Node(c[i],T,qlc[i],qrc[i],0);       //µÚiÁÐ  --> ³¬¼¶»ã 
        } 
        for (int i=1;i<=n*n/2;i++) {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if (map[x1][y1] == map[x2][y2]) continue;
            if (!map[x1][y1]) swap(x1,x2) , swap(y1,y2);
            if (x1 == x2) add_Node(c[y1],c[y2],0,1,1); //Èç¹ûÔÚͬһÐÐ ¾ÍÔÚÁÐÖ®¼äÁ¬±ß 
            if (y1 == y2) add_Node(r[x1],r[x2],0,1,1); //Èç¹ûÔÚͬһÁÐ ¾ÍÔÚÐÐÖ®¼äÁ¬±ß 
        } 
        paul(); //²¹ÉÏËùÓвðµÄ±ß 
        
        //for (int i=2;i<=cnt;i+=2) if (e[i].v) printf("%d %d %d %d
",e[i].a,e[i].b,e[i].v,e[i].cost); 
            
        while (SPFA()) 
            mcf();
        //for (int i=3;i<=cnt;i+=2) if (e[i].v) printf("%d %d %d
",e[i].b,e[i].a,e[i].v);
        
        for (int i=head[ss];i;i=e[i].next) if (e[i].v) ans = -1;//ÅжÏÊÇ·ñÓнâ
        if (ans == -1) puts("-1"); else printf("%d
",ans);
    }
    return 0;
}