HDu 1565格子取数(1)(最小割/状態圧縮+DP)

4162 ワード
Problem Description
n*nの格子の碁盤をあげて、各格子の中に非負の数があります.
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
 
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
 
Output
各テストインスタンスについて、取得可能な最大和を出力します.
 
Sample Input 

   
   
   
   

    
    
    
    3
75 15 21 
75 15 28 
34 70 5

 
Sample Output 
188

 
2つの方法:
ポイントオーバーライドセット:図Gのポイントセットがなく、図中のすべてのエッジに少なくとも1つの端点がセット内にあるようにします.//最小ポイント権オーバーライドセット:ポイント権付き無方向図Gで、ポイント権の和が最小のオーバーライドセット.//ポイント独立セット:図Gの1つのポイントセットがなく、そのセット内の2つのポイントが元の図で隣接しないようにします.//最大点権独立セット:帯権無方向図Gにおいて、点権の和が最大の独立セット.//定理://1.最小ポイントオーバーライドセット=最小割合=最大ストリーム//2.最大ポイント独立セット=合計-最小ポイントオーバーライドセット
1 . 図全体について、座標と(x+y)が偶数の点を山に、座標と奇数の山に置く.図全体のため、座標と偶数の任意の2点は隣接していないので、座標と奇数のも同じです.
座標と偶数の点をソース点に接続し、容量は数値そのものです.座標と奇数の連結点であり、容量は数値そのものである.
各点について、上下左右の4つの点がつながっているので、この4つの点は隣接しているので、それを飲んで共存することはできません.容量はinfである.
構築されたネットワークを得た後、私たちはネットワークに対して最小の割合を求めることができて、切られた辺と最小、テーマが最大を求めるため、結果はsum-sap()です;
  
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include <iomanip>
#include<iostream>
#include<algorithm>
using namespace std ;
const int N=450 ;
const int M=N*8 ;
const int inf = 1<<30;
struct node
{
	int u,v,c,next;
}edge[M];
int pre[N],head[N],dis[N],cur[N],gap[N];
int top ;
int move[4][2]={0, 1, 0, -1, 1, 0, -1, 0};

void add(int u ,int v,int c)
{
	edge[top].u=u;
	edge[top].v=v;
	edge[top].c=c;
	edge[top].next=head[u];
	head[u]=top++;
	edge[top].u=v;
	edge[top].v=u;
	edge[top].c=0;
	edge[top].next=head[v];
	head[v]=top++;
}

int sap(int s,int t,int n)
{
	int u,v,mindis,minflow=inf,flow=0;
	memset(gap,0,sizeof(gap));
	memset(dis,0,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	for(int i=0;i<n;i++)  cur[i]=head[i] ;
	u=pre[s]=s;
	gap[0]=n;
	while(dis[s] <n)
	{
		   loop:
		   	 for(int &i=cur[u] ; i!=-1 ; i=edge[i].next)
		   	 {
		   	 	   v=edge[i].v;
		   	 	   if(edge[i].c && dis[u]==dis[v]+1)
		   	 	   {
		   	 	   	    pre[v]=u;
		   	 	   	    u=v;
		   	 	   	    if(minflow > edge[i].c)
		   	 	   	      minflow = edge[i].c ;
		   	 	   	    if(v==t)
		   	 	   	    {
		   	 	   	    	for(u=pre[v] ; v!=s ; v=u,u=pre[u])
		   	 	   	    	{
		   	 	   	    		edge[cur[u]].c -=minflow ;
		   	 	   	    		edge[cur[u]^1].c += minflow ;
		   	 	   	    	}
		   	 	   	    	flow +=minflow ;
		   	 	   	    	minflow=inf;
		   	 	   	    }
		   	 	   	   goto loop ;
		   	 	   }
		   	 }
		   
		   mindis=n;
		   for(int i=head[u];i!=-1 ; i=edge[i].next)
		   {
		   	    v=edge[i].v;
		   	   if(edge[i].c>0 && dis[v] < mindis)
		   	   {
		   	   	     mindis=dis[v];
		   	   	     cur[u]=i;
		   	   }
		   }
		   if((--gap[dis[u]]) ==0)  break;
		   gap[dis[u]=mindis+1]++;
		   u=pre[u];
	}
	return flow ;
}

int main()
{
	int n ,x ,sum;
	while(~scanf("%d",&n))
	{
	       top=0;sum=0;
	       memset(head,-1,sizeof(head));
	       int s=0,t=n*n+1 ;
	       for(int i = 1 ; i <= n ; i++)
	         for(int j = 1 ; j <= n ; j++)
	          {
	          	    int tmp=(i-1)*n+j ;
					scanf("%d",&x);
	          	    if((i+j)%2==0)        //  
	          	       add(s,tmp,x);
	          	    else
	          	       add(tmp,t,x)   ;
	          	       sum+=x;
	          }
	      for(int i = 1 ; i <= n ; i++)
	         for(int j = 1 ; j <= n ; j++)
	           if((i+j)%2==0)                // ； 
	           {
	        	      int tmp=(i-1)*n+j;
	        	      if(i>1)   add(tmp,tmp-n,inf) ;     // ； 
                      if(i<n)   add(tmp,tmp+n,inf) ;   	        	
	        	      if(j<n)   add(tmp,tmp+1,inf) ;
	        	      if(j>1)   add(tmp,tmp-1,inf) ;	        	      
	           }
	         int ans=sap(s,t,t+1);
			 printf("%d
",sum-ans) ;  
	}
	 return 0;
}

 
WinAPI/COMインタフェースの使用時の呼び出し規則
1095:時間間隔(マルチインスタンステスト)ZZZULIOJ