hdu4975 行列和构造矩阵（dp判断唯一性）

题意：

和hdu4888一样，只不过是数据加强了，就是给你行列的和，让你构造一个矩阵，然后判断矩阵是否唯一。

思路：

构造矩阵很简单，跑一次最大流就行了，关键是判断矩阵的唯一性，之前的那个4888我用的是深搜找环过的，这个题目就TLE了，数据加强了，对于判断矩阵的唯一性我们可以这么想假如某一行的i列和j列满足 i列的这个> 0 && j列的这个 < 9此时我们再在另一行找到 i列的这个< 9 && j列的这个 > 0就可以把>0 的拿出来一个放在<9的上面，这样答案就不唯一了，对于最大流跑完后的到的矩阵，如果我们暴力判断上面的哪些情况的话是大约O(n^4)这样就比DFS找环还浪费时间，所以我们要用到dp优化，dp[i][j]记录的是在当前的状态之前，是否存在在某一行中，i列<9，j列>0,这样我们就可以利用之前状态的结果来节省一层for（具体看代码），但是这样还是TLE了，我们在每个for前面加几个小优化就可以过了。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 1005

#define N_edge 600000

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

typedef struct

{

    int t ,x;

}DEP;

STAR E[N_edge];

DEP xin ,tou;

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

int deep[N_node];

int row[505] ,col[505];

int map[505][505];

int dp[505][505];

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

{

    E[++tot].to = b;

    E[tot].cost = c;

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

    list[a] = tot;

    E[++tot].to = a;

    E[tot].cost = 0;

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

    list[b] = tot;

}

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

{

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

     deep[s] = 0;

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

     queue<DEP>q;

     q.push(xin);

     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 minn(int x ,int y)

{

    return x < y ? x : y;

}

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(flow == nowflow)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 ,int mktot)

{

   int i = 1 ,j = 1 ,k;

   for(k = mktot + 1 ;k <= tot ;k += 2)

   {

      map[i][j] = E[k].cost;

      if(++j > m) {i ++ ,j = 1;}

   }

   memset(dp ,0 ,sizeof(dp));

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

   {

      if(row[i] == 0 || m * 9 == row[i])continue;

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

      {

         if(col[j] == 0 || n * 9 == col[j])continue;

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

         {

              int mk1 = 0 ,mk2 = 0;

              if(map[i][j] < 9 && map[i][k] > 0)

              {

                 if(dp[k][j]) return 1;

                 mk1 ++;

              }

              if(map[i][j] > 0 && map[i][k] < 9)

              {

                if(dp[j][k]) return 1;

                mk2 ++;

              }

              if(mk1) dp[j][k] = 1;

              if(mk2) dp[k][j] = 1;

         }

      }

   }

   return 0;

}

int main ()

{

    int n ,m ,i ,j ,s1 ,s2 ,a ,mkk;

    int t ,cas = 1;

    scanf("%d" ,&t);

    while(t--)

    {

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

       s1 = s2 = mkk = 0;

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

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

       {

          scanf("%d" ,&a);

          add(0 ,i ,a);

          s1 += a;

          if(m * 9 < a) mkk = 1;

          row[i] = a;

       }

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

       {

          scanf("%d" ,&a);

          add(i + n ,n + m + 1 ,a);

          s2 += a;

          col[i] = a;

          if(n * 9 < a) mkk = 1;

       }

       printf("Case #%d: " ,cas ++);

       if(s1 != s2 || mkk)

       {

           puts("So naive!");

           continue;

       }

       int mktot = tot + 1;

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

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

       add(i ,j + n ,9);

       int maxflow = DINIC(0 ,n + m + 1 ,n + m + 1);

       if(s1 != maxflow)

       {

           puts("So naive!");

           continue;

       }

       jude(n ,m ,mktot)? puts("So young!"):puts("So simple!");

    }

    return 0;

}

巴特西

hdu4975 行列和构造矩阵（dp判断唯一性）

最新文章

热门文章