hdu3870 基于最短路的最小割

題意:

     給你一個平面圖,讓你輸出(1,1),(n ,n)的最小割..

思路:

      看完題想都沒想直接最大流,結果TLE,想想也是 G<400*400,400*400*4>,這樣的圖逾時不冤枉,後來在網上看了題解,都說是什麼論文題目,果斷去看論文結果沒看懂,後來看了下别人的了解,自己再畫畫圖大概知道是什麼意思了,果斷是看着沒有證明的證明容易懂啊..

 把最小割轉換成最短路是有限制條件的,就是這個圖首先必須是平面圖,然後要求的這兩個點還必須是平面圖最外側的點,給你圖解就明白了,感覺文字的東西越說越蒙..

看看上面的圖就明白了吧,首先我們的目的就是要把s和t斷開,也就是找一條橫向的最短路徑把他們切斷,又因為路徑的長度是根據容量來建的,是以最短路就是最小割..好想法...

#include<stdio.h>
#include<string.h>
#include<queue>

#define N_node 165000
#define N_edge 700000
#define INF 1000000000

using namespace std;

typedef struct
{
   int to ,cost ,next;
}STAR;

STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node];
int map[405][405];

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 = c;
   E[tot].next = list[b];
   list[b] = tot;
}

void SPFA(int s ,int n)
{
   for(int i = 0 ;i <= n ;i ++)
   s_x[i] = INF;
   int mark[N_node] = {0};
   mark[s] = 1;
   s_x[s] = 0;
   queue<int>q;
   q.push(s);
   while(!q.empty())
   {
      int tou ,xin;
      tou = q.front();
      q.pop();
      mark[tou] = 0;
      for(int k = list[tou] ;k ;k = E[k].next)
      {
         xin = E[k].to;
         if(s_x[xin] > s_x[tou] + E[k].cost)
         {
            s_x[xin] = s_x[tou] + E[k].cost;
            if(!mark[xin])
            {
               mark[xin] = 1;
               q.push(xin);
            }
         }
      }
   }
   return ;
}

int main ()
{
   int n ,i ,j ,t;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%d" ,&n);
      for(i = 1 ;i <= n ;i ++)
      for(j = 1 ;j <= n ;j ++)
      scanf("%d" ,&map[i][j]);
      n--;
      int ss = 0 ,tt = n * n + 1;
      memset(list ,0 ,sizeof(list));
      tot = 1;
      for(i = 1 ;i <= n ;i ++)
      for(j = 1 ;j <= n ;j ++)
      {
         int now = (i - 1) * n + j;
         int to1 = (i - 1) * n + j + 1;
         int to2 = (i - 1) * n + j + n; 
         if(j != n) add(now ,to1 ,map[i][j+1]);
         if(i != n) add(now ,to2 ,map[i+1][j]);
         if(j == 1) add(ss ,now ,map[i][j]);
         if(i == n) add(ss ,now ,map[i+1][j]);
         if(j == n) add(now ,tt ,map[i][j+1]);
         if(i == 1) add(now ,tt ,map[i][j]);
      }
      SPFA(ss ,tt);
      printf("%d\n" ,s_x[tt]);
   }
   return 0;
}