POJ2396 Budget-白红宇

POJ2396 Budget

阅读量：4537 次

发布时间：2019-06-08

本文共 7777 字，大约阅读时间需要 25 分钟。

这题是真的恶心……

有源汇的上下界网络流求可行流……

首先矩阵的建图基本比较清晰，就是行列之间连边，其上下界由给定的条件决定。这题其实有两种改造法都能过。第一种是最正统的套路，就是首先建立原点和汇点，然后把行向原点连边，容量全都是0（因为上下界的差值是0），不过要更改这些点的流入和流出下限，中间的边还是按上界减去下界为容量。这样我们现在形成了一个有源汇的上下界网络流，只要加上一条从汇点到原点容量为INF的一条边，它就成了一个无源汇的上下界网络流。然后建立辅助源汇点跑流即可。

第二种比较简洁，就是不建立源汇点，只把矩阵行列之间的边构造出来之后，直接建立辅助源汇点跑流。这样其实也是正确的，为啥呢……因为其实第一种和第二种的不同在于，他多了源汇点……但是因为源汇点直接为了转换为无源汇的图，又加上了一条INF的边，这样的话流就可以无限的从这里跑了……所以第一种多出来的流最后也没有用上……（以上都是感性理解orz……其实我也不能详细证明为啥都行）

然后就这么建图这题就可以过了。但是这题的建图是真的恶心……尤其是如果你没有使用邻接矩阵存流的下届……我是用下标计算处理的……debug到痛不欲生……看一下两种代码吧。

第一种：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define fr friend inline#define y1 poj#define mp make_pair#define pr pair
             
              #define fi first#define sc second#define pb push_backusing namespace std;typedef long long ll;const int M = 1000005;const int N = 505;const int INF = 0x3f3f3f3f;const double eps = 1e-7;int read(){ int ans = 0,op = 1;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();} while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar(); return ans * op;}struct edge{ int next,to,from,v;}e[M<<1];int Ti,n,m,head[N<<1],ecnt,x,y,a[M<<1],b[M<<1];int rsum[N<<1],csum[N<<1],S,T,tot,dep[N<<1],cur[N<<1];int hsum[N<<1],lsum[N<<1],S1,T1,k,z;queue 
              
                q;char s[3];bool flag;void add(int x,int y,int z){ e[++ecnt].to = y; e[ecnt].from = x; e[ecnt].next = head[x]; e[ecnt].v = z; head[x] = ecnt;}void build(){ x = read(),y = read(),scanf("%s",s),z = read(); if(s[0] == '>') { z++; if((z > hsum[x] && x != 0) || (z > lsum[y] && y != 0)) flag = 1; if(x == 0 && y == 0) rep(i,1,n*m) a[i] = z; else if(x == 0) rep(i,0,n-1) a[i*m+y] = z; else if(y == 0) rep(i,1,m) a[(x-1)*m+i] = z; else a[(x-1)*m+y] = z; } if(s[0] == '<') { z--; if(x == 0 && y == 0) rep(i,1,n*m) b[i] = z; else if(x == 0) rep(i,0,n-1) b[i*m+y] = z; else if(y == 0) rep(i,1,m) b[(x-1)*m+i] = z; else b[(x-1)*m+y] = z; } if(s[0] == '=') { if((z > hsum[x] && x != 0) || (z > lsum[y] && y != 0)) flag = 1; if(x == 0 && y == 0) rep(i,1,n*m) a[i] = b[i] = z; else if(x == 0) rep(i,0,n-1) a[i*m+y] = b[i*m+y] = z; else if(y == 0) rep(i,1,m) a[(x-1)*m+i] = b[(x-1)*m+i] = z; else a[(x-1)*m+y] = b[(x-1)*m+y] = z; }}void rebuild(){ rep(i,S,T) { int now = csum[i] - rsum[i]; if(now < 0) add(S1,i,-now),add(i,S1,0); else add(i,T1,now),add(T1,i,0),tot += now; }}void clear(){ flag = 0; memset(head,-1,sizeof(head)),ecnt = -1,tot = 0; memset(a,0,sizeof(a)),memset(b,0x3f,sizeof(b)); rep(i,S,T1) rsum[i] = csum[i] = 0;}bool bfs(int s,int t){ while(!q.empty()) q.pop(); rep(i,0,t) cur[i] = head[i]; memset(dep,-1,sizeof(dep)); dep[s] = 0,q.push(s); while(!q.empty()) { int k = q.front();q.pop(); for(int i = head[k];~i;i = e[i].next) { if(e[i].v && dep[e[i].to] == -1) dep[e[i].to] = dep[k] + 1,q.push(e[i].to); } } return dep[t] != -1;}int dfs(int s,int t,int lim){ if(s == t || !lim) return lim; int flow = 0; for(int i = cur[s];~i;i = e[i].next) { cur[s] = i; if(dep[e[i].to] != dep[s] + 1) continue; int f = dfs(e[i].to,t,min(lim,e[i].v)); if(f) { e[i].v -= f,e[i^1].v += f; flow += f,lim -= f; if(!lim) break; } } if(!flow) dep[s] = -1; return flow;}int dinic(int s,int t){ int maxflow = 0; while(bfs(s,t)) maxflow += dfs(s,t,INF); return maxflow;}int main(){ //freopen("a.in","r",stdin); //freopen("f.out","w",stdout); Ti = read(); while(Ti--) { n = read(),m = read(),T = n + m + 1,S1 = T + 1,T1 = S1 + 1; clear(); rep(i,1,n) hsum[i] = read(); rep(i,1,m) lsum[i] = read(); k = read(); rep(i,1,k) build(); rep(i,1,n) rep(j,1,m) { int f = a[(i-1)*m+j],g = b[(i-1)*m+j]; add(i,j+n,g-f),add(j+n,i,0); csum[i] += f,rsum[j+n] += f; } rep(i,1,n) add(S,i,0),add(i,S,0),csum[S] += hsum[i],rsum[i] += hsum[i]; rep(i,1,m) add(i+n,T,0),add(T,i+n,0),csum[i+n] += lsum[i],rsum[T] += lsum[i]; add(T,S,INF),add(S,T,0); rebuild(); int g = dinic(S1,T1); if(flag || tot > g) printf("IMPOSSIBLE\n"); else { rep(i,1,n) { rep(j,1,m) { int g = (i - 1) * m + j - 1; printf("%d ",e[g<<1|1].v + a[g+1]); } enter; } } } return 0;}

第二种：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define fr friend inline#define y1 poj#define mp make_pair#define pr pair
             
              #define fi first#define sc second#define pb push_backusing namespace std;typedef long long ll;const int M = 1000005;const int N = 505;const int INF = 0x3f3f3f3f;const double eps = 1e-7;int read(){ int ans = 0,op = 1;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();} while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar(); return ans * op;}struct edge{ int next,to,from,v;}e[M<<1];int Ti,n,m,head[N<<1],ecnt,x,y,a[M<<1],b[M<<1];int rsum[N<<1],csum[N<<1],S,T,tot,dep[N<<1],cur[N<<1];int hsum[N<<1],lsum[N<<1],S1,T1,k,z;queue 
              
                q;char s[3];bool flag;void add(int x,int y,int z){ e[++ecnt].to = y; e[ecnt].from = x; e[ecnt].next = head[x]; e[ecnt].v = z; head[x] = ecnt;}void build(){ x = read(),y = read(),scanf("%s",s),z = read(); if(s[0] == '>') { z++; if((z > hsum[x] && x != 0) || (z > lsum[y] && y != 0)) flag = 1; if(x == 0 && y == 0) rep(i,1,n*m) a[i] = z; else if(x == 0) rep(i,0,n-1) a[i*m+y] = z; else if(y == 0) rep(i,1,m) a[(x-1)*m+i] = z; else a[(x-1)*m+y] = z; } if(s[0] == '<') { z--; if(x == 0 && y == 0) rep(i,1,n*m) b[i] = z; else if(x == 0) rep(i,0,n-1) b[i*m+y] = z; else if(y == 0) rep(i,1,m) b[(x-1)*m+i] = z; else b[(x-1)*m+y] = z; } if(s[0] == '=') { if((z > hsum[x] && x != 0) || (z > lsum[y] && y != 0)) flag = 1; if(x == 0 && y == 0) rep(i,1,n*m) a[i] = b[i] = z; else if(x == 0) rep(i,0,n-1) a[i*m+y] = b[i*m+y] = z; else if(y == 0) rep(i,1,m) a[(x-1)*m+i] = b[(x-1)*m+i] = z; else a[(x-1)*m+y] = b[(x-1)*m+y] = z; }}void rebuild(){ rep(i,S,T) { int now = csum[i] - rsum[i]; //printf("%d %d\n",i,now); if(now < 0) add(S1,i,-now),add(i,S1,0); else add(i,T1,now),add(T1,i,0),tot += now; }}void clear(){ flag = 0; memset(head,-1,sizeof(head)),ecnt = -1,tot = 0; memset(a,0,sizeof(a)),memset(b,0x3f,sizeof(b)); rep(i,S,T1) rsum[i] = csum[i] = 0;}bool bfs(int s,int t){ while(!q.empty()) q.pop(); rep(i,0,t) cur[i] = head[i]; memset(dep,-1,sizeof(dep)); dep[s] = 0,q.push(s); while(!q.empty()) { int k = q.front();q.pop(); for(int i = head[k];~i;i = e[i].next) { if(e[i].v && dep[e[i].to] == -1) dep[e[i].to] = dep[k] + 1,q.push(e[i].to); } } return dep[t] != -1;}int dfs(int s,int t,int lim){ if(s == t || !lim) return lim; int flow = 0; for(int i = cur[s];~i;i = e[i].next) { cur[s] = i; if(dep[e[i].to] != dep[s] + 1) continue; int f = dfs(e[i].to,t,min(lim,e[i].v)); if(f) { e[i].v -= f,e[i^1].v += f; flow += f,lim -= f; if(!lim) break; } } if(!flow) dep[s] = -1; return flow;}int dinic(int s,int t){ int maxflow = 0; while(bfs(s,t)) maxflow += dfs(s,t,INF); return maxflow;}int main(){ //freopen("a.in","r",stdin); //freopen("f.out","w",stdout); Ti = read(); while(Ti--) { n = read(),m = read(),T = n + m + 1,S1 = T + 1,T1 = S1 + 1; clear(); rep(i,1,n) hsum[i] = read(),rsum[i] += hsum[i]; rep(i,1,m) lsum[i] = read(),csum[i+n] += lsum[i]; k = read(); rep(i,1,k) build(); rep(i,1,n) rep(j,1,m) { int f = a[(i-1)*m+j],g = b[(i-1)*m+j]; add(i,j+n,g-f),add(j+n,i,0); csum[i] += f,rsum[j+n] += f; } rebuild(); int g = dinic(S1,T1); if(flag || tot > g) printf("IMPOSSIBLE\n"); else { rep(i,1,n) { rep(j,1,m) { int g = (i - 1) * m + j - 1; printf("%d ",e[g<<1|1].v + a[g+1]); } enter; } } } return 0;}

转载于:https://www.cnblogs.com/captain1/p/10134811.html

你可能感兴趣的文章