POJ 2396 构造矩阵（上下流）

题意：

要求构造一个矩阵，给你行和，列和，还有一些点的上下范围，输出一个满足题意的矩阵。

思路：

这个题目很经典，这是自己看上下流后接触的第一道题，感觉很基础的一道题目，现在我们来分析下，如果这个题目是只给行和，列和，让我们构造矩阵应该很简单了，直接一遍最大流，然后判断是否满流，满流就把残余网络拿出来，整理下就是答案了，关键这个题

目就是不但要求满流，某些点还有上限制，或者下限制，那么就直接是上下流呗，对了还有一个地方提醒一下，在建图之前判断一下有没有输入数据冲突的情况，下面说关键部分，也就是建图，建图之前定义几个变量，s(源点),t（汇点）,ss（超级源点）,tt（超级汇点）.

s连接所有的行i add(s ,i ,行和 , 行和);

所有的列j连接终点t add(j ,t ,列和，列和);

建立一条t -> s add(t ,s ,0 ,INF);//为了把有源汇的最大流变成无源的

对于任意两点i,j add(i ,j ,下限，上限);

简单说下上下界网络流可行流判断

首先，可行流的判断就是根据在流里面，任意点的流入和流出永远都必须是相等的。

对于一个加边操作，a -> b ,下界上界可以这样处理

a -> b 流量为上界减去下界这个可以叫自由边（就是不是必须流的边）

a -> tt ,ss -> b 流量都是下界这两个叫做必须边，要想有解，必须边最后必须满流

如果是有源的，那么我们就 add(t ,s ,0 ,INF);变成无源

最后跑一遍 ss,tt的最大流，如果满流则有可行解，输出答案的话知道把所有自由边拿出来，加上下限就可以了。（因为此时下限已满流）.

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 240

#define N_edge 50000

#define INF 1000000000

using namespace std;

typedef struct

{

   int from ,to ,next ,cost;

}STAR;

typedef struct

{

   int x ,t;

}DEP;

STAR E[N_edge];

DEP xin ,tou;

int list[N_node] ,listt[N_node] ,tot;

int deep[N_node] ,sum_must;

int map[220][22][3];

int Ans[220][22];

int maxx(int x ,int y)

{

   return x > y ? x : y;

}

int minn(int x ,int y)

{

   return x < y ? x : y;

}

void add(int a ,int b ,int c)

{

   E[++tot].from = a;

   E[tot].to = b;

   E[tot].cost = c;

   E[tot].next = list[a];

   list[a] = tot;

   E[++tot].from = b;

   E[tot].to = a;

   E[tot].cost = 0;

   E[tot].next = list[b];

   list[b] = tot;

}

void ADD(int a ,int b ,int c ,int d ,int ss ,int tt)

{

   add(a ,b ,d - c);

   add(a ,tt ,c);

   add(ss ,b ,c);

   sum_must += c;

}

bool BFS_Deep(int s ,int t ,int n)

{

   xin.x = s ,xin.t = 0;

   queue<DEP>q;

   q.push(xin);

   memset(deep ,255 ,sizeof(deep));

   deep[s] = 0;

   while(!q.empty())

   {

      tou = q.front();

      q.pop();

      for(int k = list[tou.x] ;k ;k = E[k].next)

      {

         xin.x = E[k].to;

         xin.t = tou.t + 1;

         if(deep[xin.x] != -1 || !E[k].cost)

         continue;

         deep[xin.x] = xin.t;

         q.push(xin);

      }

   }

   for(int i = 0 ;i <= n ;i ++)

   listt[i] = list[i];

   return deep[t] != -1;

}

int DFS_Flow(int s ,int t ,int flow)

{

   if(s == t) return flow;

   int nowflow = 0;

   for(int k = listt[s] ;k ;k = E[k].next)

   {

      listt[s] = k;

      int to = E[k].to;

      int c  = E[k].cost;

      if(deep[to] != deep[s] + 1 || !c)

      continue;

      int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));

      nowflow += tmp;

      E[k].cost -= tmp;

      E[k^1].cost += tmp;

      if(nowflow == flow) break;

   }

   if(!nowflow) deep[s] = 0;

   return nowflow;

}

int DINIC(int s ,int t ,int n)

{

   int ans = 0;

   while(BFS_Deep(s ,t ,n))

   {

      ans += DFS_Flow(s ,t ,INF);

   }

   return ans;

}

bool jude(int n ,int m)

{

   for(int i = 1 ;i <= n ;i ++)

   for(int j = 1 ;j <= m ;j ++)

   if(map[i][j][1] > map[i][j][2]) return 0;

   return 1;

}

int main ()

{

   int a ,b ,c ,i ,j ,n ,m ,w ,T;

   char str[4];

   scanf("%d" ,&T);

   while(T--)

   {

      scanf("%d %d" ,&n ,&m);

      memset(list ,0 ,sizeof(list)) ,tot = 1;

      sum_must = 0;

      int s = 0 ,t = n + m + 1 ,ss = n + m + 2 ,tt = n + m + 3;

      for(i = 1 ;i <= n ;i ++)

      {

         scanf("%d" ,&a);

         ADD(s ,i ,a ,a ,ss ,tt);

      }

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d" ,&a);

         ADD(i + n ,t ,a ,a ,ss ,tt);

      }

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= m ;j ++)

      map[i][j][1] = 0 ,map[i][j][2] = INF;

      scanf("%d" ,&w);

      while(w--)

      {

         scanf("%d %d %s %d" ,&a ,&b ,str ,&c);

         if(a && b)

         {

            if(str[0] == '<') map[a][b][2] = minn(map[a][b][2] ,c - 1);

            if(str[0] == '=') map[a][b][1] = maxx(map[a][b][1] ,c) ,map[a][b][2] = minn(map[a][b][2] ,c);

            if(str[0] == '>') map[a][b][1] = maxx(map[a][b][1] ,c + 1);

         }

         if(a && !b)

         {

            for(j = 1 ;j <= m ;j ++)

            {

               if(str[0] == '<') map[a][j][2] = minn(map[a][j][2] ,c - 1);

               if(str[0] == '=') map[a][j][1] = maxx(map[a][j][1] ,c) ,map[a][j][2] = minn(map[a][j][2] ,c);

               if(str[0] == '>') map[a][j][1] = maxx(map[a][j][1] ,c + 1);

            }

         }

         if(!a && b)

         {

            for(j = 1 ;j <= n ;j ++)

            {

               if(str[0] == '<') map[j][b][2] = minn(map[j][b][2] ,c - 1);

               if(str[0] == '=') map[j][b][1] = maxx(map[j][b][1] ,c) ,map[j][b][2] = minn(map[j][b][2] ,c);

               if(str[0] == '>') map[j][b][1] = maxx(map[j][b][1] ,c + 1);

            }

         }

         if(!a && !b)

         {

            for(i = 1 ;i <= n ;i ++)

            for(j = 1 ;j <= m ;j ++)

            {

               if(str[0] == '<') map[i][j][2] = minn(map[i][j][2] ,c - 1);

               if(str[0] == '=') map[i][j][1] = maxx(map[i][j][1] ,c) ,map[i][j][2] = minn(map[i][j][2] ,c);

               if(str[0] == '>') map[i][j][1] = maxx(map[i][j][1] ,c + 1);

            }

         }

      }

      if(!jude(n ,m))

      {

         puts("IMPOSSIBLE");

         continue;

      }

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= m ;j ++)

      ADD(i ,j + n ,map[i][j][1] ,map[i][j][2] ,ss ,tt);

      ADD(t ,s ,0 ,INF ,ss ,tt);

      int Flow = DINIC(ss ,tt ,tt);

      if(Flow != sum_must)

      {

         puts("IMPOSSIBLE");

         continue;

      }

      for(i = 2 ;i <= tot ;i ++)

      if(E[i].from >= 1 && E[i].from <= n && E[i].to >= n + 1 && E[i].to <= n + m)

      Ans[E[i].from][E[i].to - n] = E[i^1].cost + map[E[i].from][E[i].to - n][1];

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= m ;j ++)

      if(j == m)printf("%d\n" ,Ans[i][j]);

      else printf("%d " ,Ans[i][j]);

      if(T) puts("");

   }

   return 0;

}

巴特西

POJ 2396 构造矩阵（上下流）

最新文章

热门文章